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: https://link.springer.com/chapter/10.1007%2F3-540-...
Related URL: http://dx.doi.org/10.1007/3-540-58201-0_63
Abstract
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
