|
|||||
|
|
A hierarchy of deterministic context-free ω-languages |
|
| Authors: | J. Duparc |
| Affiliation: | Equipe de Logique Mathémathique, CNRS URA 753 et Université Paris VII, U.F.R. de Mathématiques, 2 place Jussieu, 75251, Paris Cedex 05, France |
| Abstract: | Twenty years ago, Klaus. W. Wagner came up with a hierarchy of ω-regular sets that actually bears his name. It turned out to be exactly the Wadge hierarchy of the sets of ω-words recognized by deterministic finite automata. We describe the Wadge hierarchy of context-free ω-languages, which stands as an extension of Wagner's work from automata to pushdown automata. |
| Keywords: | Deterministic context-free ω-languages Pushdown automata Wadge hierarchy |
| 本文献已被 ScienceDirect 等数据库收录！ | |