On some variants of Post's correspondence problem (Q792770): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56095058 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12: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
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
0 references