Undecidability of infinite post correspondence problem for instances of size 8

DOI10.1051/ita/2012015zbMath1257.03069OpenAlexW2125797022MaRDI QIDQ2905329

Jing Dong, Qing-Hui Liu

Publication date: 27 August 2012

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

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

zbMATH Keywords

undecidabilitytheory of computationsemi-Thue system\(\omega \)PCP

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) Thue and Post systems, etc. (03D03)

Related Items (6)

Porous invariants ⋮ Integer weighted automata on infinite words ⋮ Weighted Automata on Infinite Words in the Context of Attacker-Defender Games ⋮ Integer Weighted Automata on Infinite Words ⋮ On bi-infinite and conjugate post correspondence problems ⋮ Weighted automata on infinite words in the context of attacker-defender games

Cites Work

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

This page was built for publication: Undecidability of infinite post correspondence problem for instances of size 8