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

DOI10.1007/S00153-020-00737-4zbMATH Open1498.03104arXiv2006.08174OpenAlexW3034452194MaRDI QIDQ2219094FDOQ2219094

Authors: Olivier Finkel, Dominique Lecomte 

Publication date: 19 January 2021

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

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 .

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Descriptive set theory
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• Title not available (Why is that?)
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Title not available (Why is that?)
• Topological properties of omega context-free languages
• Title not available (Why is that?)
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
• Title not available (Why is that?)
• Borel hierarchy and omega context free languages.
• An \(\omega\)-power of a context-free language which is Borel above \(\Delta^0_{\omega}\)
• Title not available (Why is that?)
• Classical and effective descriptive complexities of \(\omega \)-powers
• There Exist Some ω-Powers of Any Borel 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
• Title not available (Why is that?)

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)