A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Extension of the decidability of the marked PCP to instances with unique blocks
Tekijät: Halava V, Harju T, Karhumaki J, Latteux M
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2007
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 380
Numero: 3
Aloitussivu: 355
Lopetussivu: 362
Sivujen määrä: 8
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2007.03.024
Tiivistelmä
In the Post Correspondence Problem (PCP) an instance (h, g) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h(w) = g(w). Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances. (c) 2007 Elsevier B.V. All rights reserved.
In the Post Correspondence Problem (PCP) an instance (h, g) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h(w) = g(w). Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances. (c) 2007 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali