Name
Title | ||
|---|---|---|
About the Effect of the Number of Successful Paths in an Infinite Tree on the Recognizability by a Finite Automaton with Büchi Conditions |
Abstract | ||
|---|---|---|
We modify an acceptance condition of Büchi automaton on infinite trees: rather than to require that each computation path is successful, we impose various restrictions on the number of successful paths in a run of the automaton on a tree. All these modifications alter the recognizing power of Büchi automata. We examine the classes induced by the acceptance conditions that require , , = successful paths, where is a cardinal number. It turns out that, except some trivial cases, the classes are uncomparable with the class Bü of Büchi acceptable tree languages, while the classes are strictly included in Bü. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/3-540-54458-5_58 | FCT |
Keywords | Field | DocType |
infinite tree,chi conditions,successful paths,finite automaton | Discrete mathematics,Two-way deterministic finite automaton,Combinatorics,Deterministic automaton,Powerset construction,Timed automaton,Pushdown automaton,Probabilistic automaton,Mathematics,ω-automaton,Büchi automaton | Conference |
Volume | ISSN | ISBN |
529 | 0302-9743 | 3-540-54458-5 |
Citations | PageRank | References |
2 | 0.44 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Danièle Beauquire | 1 | 2 | 0.44 |
| Maurice Nivat | 2 | 1261 | 277.74 |
| Damian Niwinski | 3 | 489 | 71.40 |