A1 Refereed original research article in a scientific journal
Flatwords and post correspondence problem
Authors: Harju T, Lipponen M, Mateescu A
Publisher: ELSEVIER SCIENCE BV
Publication year: 1996
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 161
Issue: 1-2
First page : 93
Last page: 108
Number of pages: 16
ISSN: 0304-3975
DOI: https://doi.org/10.1016/0304-3975(95)00092-5
Abstract
We investigate properties of flatwords and k-flatwords. In particular, these words are studied in connection with Post Correspondence Problem (PCP). An open problem occurs: where is the borderline between the decidability and the undecidability of k-flat PCP over an alphabet with n symbols? Our main results concern the related new types of prime solutions of PCP.
We investigate properties of flatwords and k-flatwords. In particular, these words are studied in connection with Post Correspondence Problem (PCP). An open problem occurs: where is the borderline between the decidability and the undecidability of k-flat PCP over an alphabet with n symbols? Our main results concern the related new types of prime solutions of PCP.
UTU Research Portal