Name
Abstract | ||
|---|---|---|
Asynchronous automata are parallel compositions of finitestate processes synchronizing over shared variables. A deep theorem due to Zielonka says that every regular trace language can be represented by a deterministic asynchronous automaton. In this paper we improve the construction, in that the size of the obtained asynchronous automaton is polynomial in the size of a given DFA and simply exponential in the number of processes. We show that our construction is optimal within the class of automata produced by Zielonka-type constructions. In particular, we provide the first non trivial lower bound on the size of asynchronous automata. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14162-1_5 | ICALP (2) |
Keywords | Field | DocType |
parallel composition,zielonka-type construction,regular trace language,deterministic asynchronous automaton,asynchronous automaton,shared variable,optimal zielonka-type construction,lower bound | Quantum finite automata,Discrete mathematics,Two-way deterministic finite automaton,Combinatorics,Automata theory,Asynchronous cellular automaton,Deterministic automaton,Nondeterministic finite automaton,Computer science,DFA minimization,Timed automaton | Conference |
Volume | ISSN | ISBN |
6199 | 0302-9743 | 3-642-14161-7 |
Citations | PageRank | References |
13 | 0.60 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Blaise Genest | 1 | 304 | 25.09 |
| Hugo Gimbert | 2 | 249 | 21.31 |
| Anca Muscholl | 3 | 1179 | 74.92 |
| Igor Walukiewicz | 4 | 1239 | 90.24 |