Name
Abstract | ||
|---|---|---|
The well-known algorithm of Zielonka describes how to transform automatically a sequential automaton into a deterministic asynchronous trace automaton. In this paper, we improve the construction of deterministic asynchronous automata from finite state automaton. Our construction improves the well-known construction in that the size of the asynchronous automaton is simply exponential in both the size of the sequential automaton and the number of processes. In contrast, Zielonka's algorithm gives an asynchronous automaton that is doubly exponential in the number of processes (and simply exponential in the size of the automaton) |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11787006_48 | ICALP (2) |
Keywords | Field | DocType |
sequential automaton,deterministic asynchronous trace automaton,deterministic asynchronous automaton,asynchronous automaton,finite state automaton,well-known algorithm,well-known construction | Discrete mathematics,Combinatorics,Two-way deterministic finite automaton,Continuous automaton,Nondeterministic finite automaton,Deterministic automaton,Computer science,Algorithm,Timed automaton,Pushdown automaton,Probabilistic automaton,Büchi automaton | Conference |
Volume | ISSN | ISBN |
4052 | 0302-9743 | 3-540-35907-9 |
Citations | PageRank | References |
11 | 0.59 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Blaise Genest | 1 | 304 | 25.09 |
| Anca Muscholl | 2 | 1179 | 74.92 |