A1 Refereed original research article in a scientific journal

Generalized PCP is decidable for marked morphisms



Authors: Halava V, Harju T, Hirvensalo M

Publication year: 1999

Journal:: Lecture Notes in Computer Science

Journal name in source: FUNDAMENTALS OF COMPUTATION THEORY

Journal acronym: LECT NOTES COMPUT SC

Volume: 1684

First page : 304

Last page: 315

Number of pages: 12

ISBN: 3-540-66412-2

ISSN: 0302-9743


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 13:43