Generalized PCP is decidable for marked morphisms



: Halava V, Harju T, Hirvensalo M

: 1999

Lecture Notes in Computer Science

FUNDAMENTALS OF COMPUTATION THEORY

: LECT NOTES COMPUT SC

: 1684

: 304

: 315

: 12

: 3-540-66412-2

: 0302-9743


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.



Last updated on 2025-13-10 at 13:43