A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost confluent and preperfect Thue systems

Colm Ó Dúnlaing, Natalie Schluter

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

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 languageEnglish
JournalTheoretical Computer Science
Volume411
Pages (from-to)677-690
Number of pages14
ISSN0304-3975
Publication statusPublished - 2010
Externally publishedYes

Keywords

  • Palindromes
  • Church–Rosser Language
  • Jurdziński and Loryś
  • Computation Graphs

Fingerprint

Dive into the research topics of 'A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost confluent and preperfect Thue systems'. Together they form a unique fingerprint.

Cite this