Undecidability of infinite post correspondence problem for instances of Size 9
DOI10.1051/ITA:2006039zbMATH Open1114.03035OpenAlexW2172004614MaRDI QIDQ3423136FDOQ3423136
Authors: Vesa Halava, Tero 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
Recommendations
- Undecidability of infinite Post correspondence problem for instances of size 8
- scientific article; zbMATH DE number 2051181
- Decidability of the binary infinite Post Correspondence Problem
- The exact complexity of the infinite Post Correspondence Problem
- A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem
- An undecidable problem in correspondence theory
- Highly Undecidable Problems For Infinite Computations
- More decidable instances of Post's correspondence problem: beyond counting
- Infinite versions of some problems from finite complexity theory
- Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
Combinatorics on words (68R15) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40)
Cites Work
- A variant of a recursively unsolvable problem
- Undecidable problems for probabilistic automata of fixed dimension
- Decision problems for semi-Thue systems with a few rules
- Title not available (Why is that?)
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Remarks on generalized Post Correspondence Problem
- Decidability of the binary infinite Post Correspondence Problem
- Binary (generalized) Post Correspondence Problem
- Title not available (Why is that?)
Cited In (15)
- Porous invariants
- Integer weighted automata on infinite words
- Integer Weighted Automata on Infinite Words
- Post Correspondence Problem and Small Dimensional Matrices
- Post correspondence problem for short words
- Weighted automata on infinite words in the context of attacker-defender games
- The exact complexity of the infinite Post Correspondence Problem
- Extension of the decidability of the marked PCP to instances with unique blocks
- Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
- Undecidability of infinite Post correspondence problem for instances of size 8
- Porous invariants for linear systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Monniaux problem in abstract interpretation
- Weighted Automata on Infinite Words in the Context of Attacker-Defender Games
This page was built for publication: Undecidability of infinite post correspondence problem for instances of Size 9
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3423136)
