A1 Refereed original research article in a scientific journal

Generalized post correspondence problem for marked morphisms



Authors: Halava V, Harju T, Hirvensalo M

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

Publication year: 2000

Journal:: International Journal of Algebra and Computation

Journal name in source: INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION

Journal acronym: INT J ALGEBR COMPUT

Volume: 10

Issue: 6

First page : 757

Last page: 772

Number of pages: 16

ISSN: 0218-1967

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


Abstract
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.


Research Areas



Last updated on 2025-13-10 at 14:06