Undecidability of infinite post correspondence problem for instances of size 8
From MaRDI portal
Publication:2905329
DOI10.1051/ita/2012015zbMath1257.03069OpenAlexW2125797022MaRDI QIDQ2905329
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/
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