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.003MaRDI QIDQ844899zbMATHOpenAlexFDO

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

zbMATH Keywords

formal languagesKolmogorov complexityThue systems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086618
• Church-Rosser Thue systems and formal languages
• Regular languages are Church-Rosser congruential
• scientific article; zbMATH DE number 3898258
• The Church-Rosser property and special Thue systems

Cites work

• scientific article; zbMATH DE number 3756462 (Why is no real title available?)
• scientific article; zbMATH DE number 2086618 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 1408346 (Why is no real title available?)
• Church-Rosser Thue systems and formal languages
• Computational Complexity of One-Tape Turing Machine Computations
• Confluent and Other Types of Thue Systems
• Growing context-sensitive languages and Church-Rosser languages
• Lower bound technique for length-reducing automata
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• The undecidability of the preperfectness of Thue systems
• Une généralisation des ensembles de Dyck

Cited in

(1)

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

Describes a project that uses

Uses Software

• UCFL

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)