On some variants of Post's correspondence problem (Q792770): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q3920666 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The (generalized) Post correspondence problem with lists consisting of two words is decidable / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Remark on Code Sets and Context-Free Languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198075 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4140394 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generalized Parikh mappings and homomorphisms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5586335 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5586334 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on Post's correspondence problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3918099 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3948609 / rank
 
Normal rank

Latest revision as of 11:40, 14 June 2024

scientific article
Language Label Description Also known as
English
On some variants of Post's correspondence problem
scientific article

    Statements

    On some variants of Post's correspondence problem (English)
    0 references
    0 references
    1983
    0 references
    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.
    0 references
    decidability
    0 references
    undecidability
    0 references
    Post's Correspondence Problem
    0 references
    emptiness problem
    0 references
    linear bounded automata
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references