Name
Abstract | ||
|---|---|---|
This paper investigates acceptance conditions for finite automata recognizing omega-regular languages. As a first result, we show that, under any acceptance condition that can be defined in the MSO logic, a finite automaton can recognize at most omega-regular languages. Starting from this, the paper aims at classifying acceptance conditions according to their expressive power and at finding the exact position of the classes of omega-languages they induced according to the Borel hierarchy. A new interesting acceptance condition is introduced and fully characterized. A step forward is also made in the understanding of the expressive power of (fin, =). |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Discrete mathematics,Combinatorics,Finite-state machine,Borel hierarchy,Omega,Expressive power,Mathematics,ω-automaton |
DocType | Volume | Citations |
Journal | abs/1310.5032 | 1 |
PageRank | References | Authors |
0.37 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Cervelle | 1 | 91 | 12.01 |
| alberto dennunzio | 2 | 318 | 38.17 |
| Enrico Formenti | 3 | 400 | 45.55 |
| Julien Provillard | 4 | 51 | 6.08 |