The determinacy strength of pushdownω-languages

DOI10.1051/ITA/2017006MaRDI QIDQ5354436zbMATH OpenOpenAlexFDO

Authors Kazuyuki Tanaka, Wenjuan Li

Publication date 4 September 2017

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ita/2017006

zbMATH Keywords

2-stack visibly pushdown automataGale-Stewart gamespushdown \(\omega\)-languagesreverse mathematics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3990900
• Refined Bounds on Kolmogorov Complexity for ω-Languages
• A hierarchy of deterministic context-free \(\omega\)-languages.
• \(P\)-disjunctive \(\omega \)-languages
• scientific article; zbMATH DE number 1962805
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Logic for \(\omega\)-pushdown automata
• scientific article; zbMATH DE number 4043282
• The disjunctivities of -languages.
• scientific article; zbMATH DE number 5074397

Cited in

(8)

• Regularity problems for weak pushdown -automata and games
• Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies
• Infinite games specified by 2-tape automata
• scientific article; zbMATH DE number 1962805 (Why is no real title available?)
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Refined Bounds on Kolmogorov Complexity for ω-Languages
• scientific article; zbMATH DE number 7720787 (Why is no real title available?)
• A proof theory of ( -)context-free languages, via non-wellfounded proofs

This page was built for publication: The determinacy strength of pushdownω-languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5354436)