Generalized post correspondence problem for marked morphisms

: Halava V, Harju T, Hirvensalo M

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

: 2000

International Journal of Algebra and Computation

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION

: INT J ALGEBR COMPUT

: 10

: 6

: 757

: 772

: 16

: 0218-1967

DOI: https://doi.org/10.1142/S0218196700000376

We prove that the generalized Post Correspondence Problem (GPCP) is decidable for marked morphisms. This result gives as a corollary a shorter proof for the decidability of the binary PCP, proved in 1982 by Ehrenfeucht, Karhumaki and Rozenberg.

Mathematics