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

DOI10.1016/j.tcs.2009.10.003zbMath1184.68276OpenAlexW2068700956MaRDI QIDQ844899

Natalie Schluter, Colm P. O'Dunlaing

Publication date: 5 February 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.10.003

zbMATH Keywords

Kolmogorov complexityformal languagesThue systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

An almost-confluent congruential language which is not Church-Rosser congruential

Uses Software

• UCFL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The undecidability of the preperfectness of Thue systems
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• Growing context-sensitive languages and Church-Rosser languages
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Lower bound technique for length-reducing automata
• Une généralisation des ensembles de Dyck
• Church-Rosser Thue systems and formal languages
• Confluent and Other Types of Thue Systems
• Computational Complexity of One-Tape Turing Machine Computations