On some variants of Post's correspondence problem

DOI10.1007/BF00290732zbMath0537.68080WikidataQ56095058 ScholiaQ56095058MaRDI QIDQ792770

Keijo Ruohonen

Publication date: 1983

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

undecidabilitydecidabilitylinear bounded automataemptiness problemPost's Correspondence Problem

Mathematics Subject Classification ID

Related Items (8)

New proof for the undecidability of the circular PCP ⋮ Undecidable problems in unreliable computations. ⋮ Decidability of liveness for concurrent objects on the TSO memory model ⋮ On bi-infinite and conjugate post correspondence problems ⋮ On the \(n\)-permutation Post correspondence problem ⋮ On complete one-way functions ⋮ Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems ⋮ Undecidable verification problems for programs with unreliable channels

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

This page was built for publication: On some variants of Post's correspondence problem