A Hierarchy of Deterministic Context-Free omega-languages

Details

Serval ID
serval:BIB_85CBFB047B2B
Type
Article: article from journal or magazin.
Collection
Publications
Institution
Title
A Hierarchy of Deterministic Context-Free omega-languages
Journal
Theoretical Computer Science
Author(s)
Duparc J.
ISSN
0304-3975
Publication state
Published
Issued date
2003
Peer-reviewed
Oui
Volume
290
Number
3
Pages
1253-1300
Language
english
Abstract
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.
Keywords
Deterministic context-free omega-languages, Pushdown automata, Wadge hierarchy
Web of science
Open Access
Yes
Create date
19/11/2007 11:37
Last modification date
20/08/2019 15:45
Usage data