Growing context-sensitive languages and Church-Rosser languages
From MaRDI portal
Publication:1383712
DOI10.1006/inco.1997.2681zbMath0894.68093OpenAlexW1984896712WikidataQ60307678 ScholiaQ60307678MaRDI QIDQ1383712
Gerhard Buntrock, Friedrich Otto
Publication date: 30 August 1998
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1997.2681
Related Items (47)
The chop of languages ⋮ Regulated variants of limited context restarting automata ⋮ Weighted restarting automata and pushdown relations ⋮ The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages ⋮ Probabilistic length-reducing two-pushdown 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 ⋮ Left-to-right regular languages and two-way restarting automata ⋮ On stateless deterministic restarting automata ⋮ Asynchronous Parallel Communicating Systems of Pushdown Automata ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Unnamed Item ⋮ Input-Driven Double-Head Pushdown Automata ⋮ McNaughton families of languages. ⋮ The context-splittable normal form for Church-Rosser language systems. ⋮ Queue Automata: Foundations and Developments ⋮ A hierarchy of jumping restarting automata ⋮ Non-returning deterministic and nondeterministic finite automata with translucent letters ⋮ Sweeping input-driven pushdown automata ⋮ A hierarchy of monotone deterministic non-forgetting restarting automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Alternating Phrase-Structure Grammars ⋮ On the complexity of 2-monotone restarting automata ⋮ A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata ⋮ Linear automata with translucent letters and linear context-free trace languages ⋮ On the expressive power of stateless ordered restart-delete automata ⋮ Restarting transducers, regular languages, and rational relations ⋮ The size of Higman-Haines sets ⋮ On determinism versus nondeterminism for restarting automata ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ On state-alternating context-free grammars ⋮ The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ On Stateless Deterministic Restarting Automata ⋮ ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA ⋮ ON A GENERALIZATION OF DEHN'S ALGORITHM ⋮ On deterministic ordered restart-delete automata ⋮ On Restarting Automata with Window Size One ⋮ Knapsack in hyperbolic groups ⋮ Diving into the queue ⋮ Automata with cyclic move operations for picture languages ⋮ Small overlap monoids. II: Automatic structures and normal forms. ⋮ WHEN CHURCH-ROSSER BECOMES CONTEXT FREE ⋮ Two-dimensional hierarchies of proper languages of lexicalized FRR-automata ⋮ SHRINKING RESTARTING AUTOMATA ⋮ On restarting automata with auxiliary symbols and small window size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Membership for growing context-sensitive grammars is polynomial
- Tree-size bounded alternation
- On the complexity of formal grammars
- Church-Rosser Thue systems and formal languages
- Confluent and Other Types of Thue Systems
- On the Tape Complexity of Deterministic Context-Free Languages
- Cross-sections for finitely presented monoids with decidable word problems
- On growing context-sensitive languages
- Some remarks on derivations in general rewriting systems
- Semantics of context-free languages
- Deterministic context-sensitive languages: Part II
- The parsing for general phrase-structure grammars
- One-way nondeterministic real-time list-storage languages
This page was built for publication: Growing context-sensitive languages and Church-Rosser languages
