On some variants of Post's correspondence problem
type: Item
instance of: scholarly article
title: On some variants of Post's correspondence problem
zbMATH Open document ID: 0537.68080
DOI: 10.1007/BF00290732
author: Keijo Ruohonen
published in: Acta Informatica
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 3854453
zbMATH Keywords: decidability
zbMATH Keywords: undecidability
zbMATH Keywords: Post's Correspondence Problem
zbMATH Keywords: emptiness problem
zbMATH Keywords: linear bounded automata
Wikidata QID: Q56095058
MaRDI profile type: Publication
cites work: Q3920666
cites work: The (generalized) Post correspondence problem with lists consisting of two words is decidable
cites work: A Remark on Code Sets and Context-Free Languages
cites work: Q4198075
cites work: Q4140394
cites work: Generalized Parikh mappings and homomorphisms
cites work: Q5586335
cites work: Q5586334
cites work: A note on Post's correspondence problem
cites work: Q3918099
cites work: Q3948609
DBLP publication ID: journals/acta/Ruohonen83
Recommended article: Q4729772
Recommended article: On the \(n\)-permutation Post correspondence problem
Recommended article: Some new results on Post correspondence problem and its modifications
Recommended article: Remarks on generalized Post Correspondence Problem
Recommended article: On simplest possible solutions for Post Correspondence Problems
Recommended article: Post's correspondence problem: from computer science to algebra
Recommended article: Q4510798
Recommended article: Q5485996
Recommended article: The Post correspondence problem over a unary alphabet
Recommended article: On the Dual Post Correspondence Problem
description: scientific article; zbMATH DE number 3854453