Binary (generalized) Post Correspondence Problem
type: Item
instance of: scholarly article
title: Binary (generalized) Post Correspondence Problem
zbMATH Open document ID: 1023.03038
DOI: 10.1016/S0304-3975(01)00157-8
author: Vesa Halava
author: Mika Hirvensalo
author: Tero Harju
published in: Theoretical Computer Science
publication date: 2002-07-15T00:00:00Z
review text: We give a new proof for the decidability of the binary Post Correspondence Problem (PCP) originally proved in 1982 by \textit{A. Ehrenfeucht, J. Karhumäki} and \textit{G. Rozenberg} [Theor. Comput. Sci. 21, 119-144 (1982; Zbl 0493.68076)]. Our proof is complete and somewhat shorter than the original proof although we use the same basic idea.
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1768179
zbMATH Keywords: binary Post Correspondence Problem
zbMATH Keywords: generalised Post Correspondence Problem
zbMATH Keywords: marked morphisms
zbMATH Keywords: decidability
MaRDI profile type: Publication
cites work: Q3859267
cites work: The (generalized) Post correspondence problem with lists consisting of two words is decidable
cites work: Generalized Post correspondence problem for marked morphisms
cites work: Marked PCP is decidable
cites work: Q4714446
cites work: Remarks on generalized Post Correspondence Problem
cites work: A variant of a recursively unsolvable problem
cites work: Q5678435
full work available at URL: s0304-3975(01)00157-8
OpenAlex ID: W2002889841
Wikidata QID: Q127674380
description: scientific article; zbMATH DE number 1768179