FLATWORDS AND POST CORRESPONDENCE PROBLEM

Authors
HARJU T LIPPONEN M MATEESCU A
Citation
T. Harju et al., FLATWORDS AND POST CORRESPONDENCE PROBLEM, Theoretical computer science, 161(1-2), 1996, pp. 93-108
Citations number
20
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
161
Issue
1-2
Year of publication
1996
Pages
93 - 108
Database
ISI
SICI code
0304-3975(1996)161:1-2<93:FAPCP>2.0.ZU;2-2
Abstract
We investigate properties of flatwords and k-flatwords. In particular, these words are studied in connection with Post Correspondence Proble m (PCP). An open problem occurs: where is the borderline between the d ecidability and the undecidability of k-flat PCP over an alphabet with n symbols? Our main results concern the related new types of prime so lutions of PCP.