Abstract
In 2002, Jurdziński and Loryś settled a long-standing conjecture that palindromes are not a Church–Rosser language. Their proof involved a difficult analysis of computation graphs associated with 2-pushdown-stack automata. We present a shorter and easier proof in terms of 1-tape Turing machines.We also discuss how the proof generalises to almost-confluent Thue systems and the differing powers of Church–Rosser, almost-confluent, and preperfect Thue systems in relation to palindromes.
Original language | English |
---|---|
Journal | Theoretical Computer Science |
Volume | 411 |
Pages (from-to) | 677-690 |
Number of pages | 14 |
ISSN | 0304-3975 |
Publication status | Published - 2010 |
Externally published | Yes |
Keywords
- Palindromes
- Church–Rosser Language
- Jurdziński and Loryś
- Computation Graphs