Madhavan Mukund

Determinizing Asynchronous Automata

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.