Binary (generalized) Post Correspondence Problem (Q1605309)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Binary (generalized) Post Correspondence Problem |
scientific article |
Statements
Binary (generalized) Post Correspondence Problem (English)
0 references
15 July 2002
0 references
We give a new proof for the decidability of the binary Post Correspondence Problem (PCP) originally proved in 1982 by \textit{A. Ehrenfeucht, J. Karhumäki} and \textit{G. Rozenberg} [Theor. Comput. Sci. 21, 119-144 (1982; Zbl 0493.68076)]. Our proof is complete and somewhat shorter than the original proof although we use the same basic idea.
0 references
binary Post Correspondence Problem
0 references
generalised Post Correspondence Problem
0 references
marked morphisms
0 references
decidability
0 references
0 references
