On growing context-sensitive languages
From MaRDI portal
Publication:5204308
DOI10.1007/3-540-55719-9_65zbMath1425.68186OpenAlexW1516086105MaRDI QIDQ5204308
Krzysztof Loryś, Gerhard Buntrock
Publication date: 4 December 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55719-9_65
Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
Lower bound technique for length-reducing automata ⋮ \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata ⋮ Growing context-sensitive languages and Church-Rosser languages ⋮ On weak growing context-sensitive grammars ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Membership for growing context-sensitive grammars is polynomial
- Isomorphisms and 1-L reductions
- Properties that characterize LOGCFL
- On the complexity of formal grammars
- Normal forms for context-sensitive grammars
- On the Tape Complexity of Deterministic Context-Free Languages
- Studies in abstract families of languages
- The parsing for general phrase-structure grammars
- An infinite hierarchy of intersections of context-free languages
- On the structure of context-sensitive grammars
This page was built for publication: On growing context-sensitive languages