A1 Refereed original research article in a scientific journal

Binary (generalized) Post Correspondence Problem



Authors: Halava V, Harju T, Hirvensalo M

Publisher: ELSEVIER SCIENCE BV

Publication year: 2002

Journal:: Theoretical Computer Science

Journal name in source: THEORETICAL COMPUTER SCIENCE

Journal acronym: THEOR COMPUT SCI

Article number: PII S0304-3975(01)00157-8

Volume: 276

Issue: 1-2

First page : 183

Last page: 204

Number of pages: 22

ISSN: 0304-3975

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


Abstract
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.


Research Areas



Last updated on 2025-13-10 at 14:57