A Hierarchy of Deterministic Context-Free omega-languages
Détails
ID Serval
serval:BIB_85CBFB047B2B
Type
Article: article d'un périodique ou d'un magazine.
Collection
Publications
Institution
Titre
A Hierarchy of Deterministic Context-Free omega-languages
Périodique
Theoretical Computer Science
ISSN
0304-3975
Statut éditorial
Publié
Date de publication
2003
Peer-reviewed
Oui
Volume
290
Numéro
3
Pages
1253-1300
Langue
anglais
Résumé
Twenty years ago, Klaus. W. Wagner came up with a hierarchy of omega-regular sets that actually bears his name. It turned out to be exactly the Wadge hierarchy of the sets of omega-words recognized by deterministic finite automata. We describe the Wadge hierarchy of context-free omega-languages, which stands as an extension of Wagner's work from automata to pushdown automata.
Mots-clé
Deterministic context-free omega-languages, Pushdown automata, Wadge hierarchy
Web of science
Open Access
Oui
Création de la notice
19/11/2007 10:37
Dernière modification de la notice
20/08/2019 14:45