A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Generalized PCP is decidable for marked morphisms
Tekijät: Halava V, Harju T, Hirvensalo M
Julkaisuvuosi: 1999
Lehti:: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: FUNDAMENTALS OF COMPUTATION THEORY
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 1684
Aloitussivu: 304
Lopetussivu: 315
Sivujen määrä: 12
ISBN: 3-540-66412-2
ISSN: 0302-9743
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