Some complete -powers of a one-counter language, for any Borel class of finite rank

DOI10.1007/S00153-020-00737-4MaRDI QIDQ2219094zbMATH OpenOpenAlexFDO

Authors Olivier Finkel, Dominique Lecomte

Publication date 19 January 2021

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.08174

zbMATH Keywords

completeBorel class\(\omega\)-powerone-counter automatoncontext-free

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05)

Abstract: We prove that, for any natural number n $ge$ 1, we can find a finite alphabet $Sigma$ and a finitary language L over $Sigma$ accepted by a one-counter automaton, such that the $omega$-power L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L} is $Pi$ 0 n-complete. We prove a similar result for the class $Sigma$ 0 n .

Recommendations

• scientific article; zbMATH DE number 2140432
• There Exist Some ω-Powers of Any Borel Rank
• New Computational Paradigms
• An \(\omega\)-power of a context-free language which is Borel above \(\Delta^0_{\omega}\)
• Borel ranks and Wadge degrees of context free $\omega$-languages

Cites work

• scientific article; zbMATH DE number 4019040 (Why is no real title available?)
• scientific article; zbMATH DE number 48095 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 2140432 (Why is no real title available?)
• scientific article; zbMATH DE number 871238 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• An \(\omega\)-power of a context-free language which is Borel above \(\Delta^0_{\omega}\)
• Borel hierarchy and omega context free languages.
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Classical and effective descriptive complexities of \(\omega \)-powers
• Descriptive set theory
• Theory of -languages. I: Characterizations of -context- free languages
• There Exist Some ω-Powers of Any Borel Rank
• Topological properties of omega context-free languages
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
• ω-powers and descriptive set theory

Cited in

(6)

• Borel ranks and Wadge degrees of context free $\omega$-languages
• On omega context free languages which are Borel sets of infinite rank.
• There Exist Some ω-Powers of Any Borel Rank
• Büchi VASS recognise \(\mathbf{\Sigma}^{1}_{1}\)-complete \({\omega}\)-languages
• Wadge degrees of \(\mathbf{\Delta}^0_2\) omega-powers
• scientific article; zbMATH DE number 2140432 (Why is no real title available?)

This page was built for publication: Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank

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