Undecidability of infinite post correspondence problem for instances of Size 9

DOI10.1051/ita:2006039zbMath1114.03035OpenAlexW2172004614MaRDI QIDQ3423136

Vesa Halava, Tero J.Harju

Publication date: 20 February 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_4_551_0

zbMATH Keywords

undecidabilityPost correspondence problem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40)

Related Items (9)

Porous invariants ⋮ Integer weighted automata on infinite words ⋮ Extension of the decidability of the marked PCP to instances with unique blocks ⋮ Undecidability of infinite post correspondence problem for instances of size 8 ⋮ Weighted Automata on Infinite Words in the Context of Attacker-Defender Games ⋮ Integer Weighted Automata on Infinite Words ⋮ THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ The exact complexity of the infinite Post Correspondence Problem

Cites Work

• Unnamed Item
• Unnamed Item
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Undecidable problems for probabilistic automata of fixed dimension
• Decidability of the binary infinite Post Correspondence Problem
• Binary (generalized) Post Correspondence Problem
• Decision problems for semi-Thue systems with a few rules
• Remarks on generalized Post Correspondence Problem
• A variant of a recursively unsolvable problem

This page was built for publication: Undecidability of infinite post correspondence problem for instances of Size 9