Binary (generalized) Post Correspondence Problem

: Halava V, Harju T, Hirvensalo M

Publisher: ELSEVIER SCIENCE BV

: 2002

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: PII S0304-3975(01)00157-8

: 276

: 1-2

: 183

: 204

: 22

: 0304-3975

DOI: https://doi.org/10.1016/S0304-3975(01)00157-8

We give a new proof for the decidability of the binary Post Correspondence Problem (PCP) originally proved in 1982 by Ehrenfeucht, Karhumaki and Rozenberg. Our proof is complete and somewhat shorter than the original proof although we use the same basic idea. (C) 2002 Elsevier Science B.V. All rights reserved.

Mathematics