Flatwords and post correspondence problem



: Harju T, Lipponen M, Mateescu A

Publisher: ELSEVIER SCIENCE BV

: 1996

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 161

: 1-2

: 93

: 108

: 16

: 0304-3975

DOI: https://doi.org/10.1016/0304-3975(95)00092-5


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.



Last updated on 2025-13-10 at 12:32