On some variants of Post's correspondence problem
From MaRDI portal
Publication:792770
DOI10.1007/BF00290732zbMath0537.68080WikidataQ56095058 ScholiaQ56095058MaRDI QIDQ792770
Publication date: 1983
Published in: Acta Informatica (Search for Journal in Brave)
undecidability; decidability; linear bounded automata; emptiness problem; Post's Correspondence Problem
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03D10: Turing machines and related notions
03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Related Items
Undecidable verification problems for programs with unreliable channels, Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems, Decidability of liveness for concurrent objects on the TSO memory model, On bi-infinite and conjugate post correspondence problems, New proof for the undecidability of the circular PCP, On the \(n\)-permutation Post correspondence problem, On complete one-way functions, Undecidable problems in unreliable computations.
Cites Work
- A note on Post's correspondence problem
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Generalized Parikh mappings and homomorphisms
- A Remark on Code Sets and Context-Free Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item