Determinizing asynchronous automata

Klarlund, Nils ; Mukund, Madhavan ; Sohoni, Milind (2005) Determinizing asynchronous automata In: 21st International Colloquium on Automata, Languages, and Programming (ICALP 1994), 11-14 Jul 1994, Jerusalem, Israel.

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
ID Code:114250
Deposited On:25 May 2018 04:57
Last Modified:25 May 2018 04:57

Repository Staff Only: item control page