The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages

DOI10.1016/j.ic.2004.09.003zbMath1075.68046OpenAlexW2155704531MaRDI QIDQ1776398

Gundula Niemann, Friedrich Otto

Publication date: 12 May 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.09.003

zbMATH Keywords

Automata and formal languagesString rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (25)

The chop of languages ⋮ Probabilistic length-reducing two-pushdown automata ⋮ Nondeterministic Ordered Restarting Automata ⋮ A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems ⋮ Lower bound technique for length-reducing automata ⋮ Degrees of non-monotonicity for restarting automata ⋮ Left-to-right regular languages and two-way restarting automata ⋮ On stateless deterministic restarting automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A survey on the local divisor technique ⋮ Input-Driven Double-Head Pushdown Automata ⋮ A hierarchy of jumping restarting automata ⋮ A hierarchy of monotone deterministic non-forgetting restarting automata ⋮ Unnamed Item ⋮ On the complexity of 2-monotone restarting automata ⋮ The size of Higman-Haines sets ⋮ On determinism versus nondeterminism for restarting automata ⋮ Two-Sided Strictly Locally Testable Languages ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ Star-free languages are Church-Rosser congruential ⋮ On Stateless Deterministic Restarting Automata ⋮ ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA ⋮ WHEN CHURCH-ROSSER BECOMES CONTEXT FREE ⋮ On restarting automata with auxiliary symbols and small window size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Growing context-sensitive languages and Church-Rosser languages
• Time-bounded grammars and their languages
• Church-Rosser Thue systems and formal languages
• Confluent and Other Types of Thue Systems
• Cross-sections for finitely presented monoids with decidable word problems
• On growing context-sensitive languages

This page was built for publication: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages