The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
From MaRDI portal
Publication:1776398
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
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
