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.