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.003zbMATH Open1184.68276OpenAlexW2068700956MaRDI QIDQ844899FDOQ844899
Authors: 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
Recommendations
Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cites Work
- Growing context-sensitive languages and Church-Rosser languages
- Title not available (Why is that?)
- Church-Rosser Thue systems and formal languages
- Computational Complexity of One-Tape Turing Machine Computations
- Une généralisation des ensembles de Dyck
- Confluent and Other Types of Thue Systems
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- The undecidability of the preperfectness of Thue systems
- Lower bound technique for length-reducing automata
- Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (1)
Uses Software
This page was built for publication: A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844899)
