A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Binary (generalized) Post Correspondence Problem
Tekijät: Halava V, Harju T, Hirvensalo M
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2002
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Artikkelin numero: PII S0304-3975(01)00157-8
Vuosikerta: 276
Numero: 1-2
Aloitussivu: 183
Lopetussivu: 204
Sivujen määrä: 22
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(01)00157-8
Tiivistelmä
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.
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.
Turun yliopiston Tutkimustietojärjestelmän portaali