A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Flatwords and post correspondence problem
Tekijät: Harju T, Lipponen M, Mateescu A
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1996
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 161
Numero: 1-2
Aloitussivu: 93
Lopetussivu: 108
Sivujen määrä: 16
ISSN: 0304-3975
DOI: https://doi.org/10.1016/0304-3975(95)00092-5
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali