A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Generalized post correspondence problem for marked morphisms
Tekijät: Halava V, Harju T, Hirvensalo M
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2000
Lehti:: International Journal of Algebra and Computation
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION
Lehden akronyymi: INT J ALGEBR COMPUT
Vuosikerta: 10
Numero: 6
Aloitussivu: 757
Lopetussivu: 772
Sivujen määrä: 16
ISSN: 0218-1967
DOI: https://doi.org/10.1142/S0218196700000376
Tiivistelmä
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.
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.
Turun yliopiston Tutkimustietojärjestelmän portaali