Name
Abstract | ||
|---|---|---|
We introduce and study three notions of typeness for automata on infinite words. For an acceptance-condition class gamma (that is, gamma is weak, Buchi, co-Buchi, Rabin, or Streett), deterministic gamma-typeness asks for the existence of an equivalent gamma-automaton on the same deterministic structure, nondeterministic gamma-typeness asks for the existence of an equivalent gamma-automaton on the same structure, and gamma-powerset-typeness asks for the existence of an equivalent gamma-automaton on the (deterministic) powerset structure - one obtained by applying the subset construction. The notions are helpful in studying the complexity and complication of translations between the various classes of automata. For example, we prove that deterministic Buchi automata are co-Buchi type; it follows that a translation from deterministic Buchi to deterministic co-Buchi automata, when exists, involves no blow up. On the other hand, we prove that nondeterministic Buchi automata are not co-Buchi type; it follows that a translation from a nondeterministic Buchi to nondeterministic co-Buchi automata, when exists, should be more complicated than just redefining the acceptance condition. As a third example, by proving that nondeterministic co-Buchi automata are Buchi-powerset type, we show that a translation of nondeterministic co-Buchi to deterministic Bidchi automata, when exists, can be done applying the subset construction. We give a complete picture of typeness for the weak, Buchi, co-Buchi, Rabin, and Streett acceptance conditions, and discuss its usefulness. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1142/S0129054106004157 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
automata on infinite words, acceptance conditions | Computer science,Automaton,Theoretical computer science,Omega | Conference |
Volume | Issue | ISSN |
3299 | 4 | 0302-9743 |
Citations | PageRank | References |
1 | 0.35 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Orna Kupferman | 1 | 3548 | 223.79 |
| Gila Morgenstern | 2 | 63 | 7.37 |
| Aniello Murano | 3 | 267 | 35.72 |