Determinizing Asynchronous Automata
DOI:
https://doi.org/10.7146/dpb.v22i460.6933Abstract
A concurrent version of a finite-state automaton is a set of processes that cooperate in processing letters of the input. Each letter read prompts some of the processes to synchronize and decide on a joint move according to a non-deterministic transition relation. Such automata are known as asynchronous automata.
The question whether these automata can be determinized while retaining the synchronization structure has already been answered is the positive, but indirectly, by Zielonka's Theorem. Unfortunately, this construction does not give an optimal solution.
In this paper we present an elementary proof, which generalizes the classic subset construction for finite-state automata. The proof uses in an essential way an earlier finite-state construction by Mukund and Sohoni for maintaining each process's latest knowledge about other processes.
Our construction is only double-exponential and thus is the first essentially to match the lower bound.
In conjunction with earlier results of Ochmanski and Pighizzini, our construction provides a new (and in a sense ''classical'') proof of Zielonka's theorem that every recognizable trace language is accepted by a deterministic asynchronous automaton whose structure precisely captures the independence relation of the given trace alphabet.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.