The exact complexity of the infinite Post Correspondence Problem

DOI10.1016/j.ipl.2015.02.009zbMath1328.68091OpenAlexW2007803218MaRDI QIDQ2345861

Olivier Finkel

Publication date: 21 May 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.02.009

zbMATH Keywords

computational complexitydecision problemsformal languagestheory of computationexact complexity\(\Pi_1^0\)-completeinfinite Post Correspondence Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On bi-infinite and conjugate post correspondence problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two decidability problems for infinite words
• \(\omega\)-computations on Turing machines
• \(\omega\)-computations on deterministic pushdown machines
• Undecidable problems for probabilistic automata of fixed dimension
• Undecidability of infinite post correspondence problem for instances of Size 9
• Index sets for ω‐languages
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE

This page was built for publication: The exact complexity of the infinite Post Correspondence Problem