THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE

DOI10.1142/S0129054112400606zbMath1267.68133arXiv1107.5886OpenAlexW3101098781MaRDI QIDQ4923292

Olivier Finkel

Publication date: 6 June 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

decision problemstopologyanalytical hierarchypoints of continuityinfinitary rational relationshigh undecidabilityinfinite Post correspondence problemomega rational functions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Thue and Post systems, etc. (03D03)

Related Items (5)

Two Effective Properties of ω-Rational Functions ⋮ Unnamed Item ⋮ Multi-buffer simulations: decidability and complexity ⋮ Topological Characterisation of Multi-Buffer Simulation ⋮ The exact complexity of the infinite Post Correspondence Problem

Cites Work

• Decision problems for Turing machines
• Two decidability problems for infinite words
• \(X\)-automata on \(\omega\)-words
• \(\omega\)-computations on Turing machines
• A theory of timed automata
• How to decide continuity of rational functions on infinite words
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Note on: ``How to decide continuity of rational functions on infinite words
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Undecidability of infinite post correspondence problem for instances of Size 9
• On the continuity set of an Omega rational function
• Highly Undecidable Problems For Infinite Computations
• Rekursive Folgenmengen I
• Index sets for ω‐languages

This page was built for publication: THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE