On some variants of Post's correspondence problem
The author proves the undecidability of several variants of Post's Correspondence Problem (PCP). The n-permutation PCP (n-PPCP) consists in finding out, for any two morphisms \(f,g:\Sigma^*_ 1\to \Sigma^*_ 2,\) whether or not \(f(A)=g(B)\) for some nonempty words A, B such that \(A=A_ 1...A_ n\) and \(B=A_{p(1)}...A_{p(n)},\) where \(A_ 1,...,A_ n\) are (possibly empty) words and p is an n-permutation; then PCP amounts to 1-PPCP. For each \(n\geq 1\), the n-PPCP is shown to be undecidable (by reducing the emptiness problem for deterministic context- sensitive languages to it via some morphisms on the instantaneous descriptions of deterministic linear bounded automata). A refinement of this proof leads to the undecidability of PCP for circular words, for doubly infinite words, and for doubly infinite powers of words. The author conjectures the undecidability of the following (n,m)-PPCP: for any morphisms f,g, find out whether or not there exists words A, B satisfying the afore-mentioned decomposition relation and such that f(A), g(B) also satisfy this relation with n replaced by m.
- scientific article; zbMATH DE number 4114608
- On the \(n\)-permutation Post correspondence problem
- Some new results on Post correspondence problem and its modifications
- Remarks on generalized Post Correspondence Problem
- On simplest possible solutions for Post Correspondence Problems
- Post's correspondence problem: from computer science to algebra
- scientific article; zbMATH DE number 1522564
- On F-prime solutions of the Post correspondence problem
- The Post correspondence problem over a unary alphabet
- On the dual Post correspondence problem
- A note on Post's correspondence problem
- A Remark on Code Sets and Context-Free Languages
- Generalized Parikh mappings and homomorphisms
- scientific article; zbMATH DE number 3730118 (Why is no real title available?)
- scientific article; zbMATH DE number 3733281 (Why is no real title available?)
- scientific article; zbMATH DE number 3767068 (Why is no real title available?)
- scientific article; zbMATH DE number 3569843 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3305030 (Why is no real title available?)
- scientific article; zbMATH DE number 3305031 (Why is no real title available?)
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Undecidable problems in unreliable computations.
- P, NP, and the Post correspondence problem
- Deterministic semi-Thue systems and variants of Post correspondence problem
- Post correspondence problem with partially commutative alphabets
- scientific article; zbMATH DE number 3976343 (Why is no real title available?)
- scientific article; zbMATH DE number 4037835 (Why is no real title available?)
- New proof for the undecidability of the circular PCP
- Remarks on generalized Post Correspondence Problem
- Undecidable verification problems for programs with unreliable channels
- The Post correspondence problem in groups.
- scientific article; zbMATH DE number 1860694 (Why is no real title available?)
- On the \(n\)-permutation Post correspondence problem
- On the dual Post correspondence problem
- Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
- A variant of a recursively unsolvable problem
- On the steps of Emil Post: from normal systems to the correspondence decision problem
- Decidability of liveness for concurrent objects on the TSO memory model
- On bi-infinite and conjugate post correspondence problems
- Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
- On complete one-way functions
- More decidable instances of Post's correspondence problem: beyond counting
- Post correspondence problem for short words
This page was built for publication: On some variants of Post's correspondence problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792770)
