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

DOI10.1142/S0129054112400606zbMath1267.68133arXiv1107.5886MaRDI 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 problems; topology; analytical hierarchy; points of continuity; infinitary rational relations; high undecidability; infinite Post correspondence problem; omega rational functions

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

03D03: Thue and Post systems, etc.

Related Items

Unnamed Item, Topological Characterisation of Multi-Buffer Simulation, Two Effective Properties of ω-Rational Functions, Multi-buffer simulations: decidability and complexity, 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