N Klarlund, M Mukund and M Sohoni
Proc. ICALP '94, Springer LNCS 820 (1994) 130-141.
© Springer-Verlag Berlin Heidelberg
An asynchronous automaton consists of 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.
Zielonka's theorem tells us that these automata can be determinized while retaining the synchronization structure. Unfortunately, this construction is indirect and yields a triple-exponential blow-up in size.
We present a direct determinization procedure for asynchronous automata which generalizes the classical subset construction for finite-state automata. Our construction is only double-exponential and thus is the first to essentially match the lower bound.
Available as a gzipped dvi (40 KB) or gzipped Postscript (79 KB) file.