On growing context-sensitive languages

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

zbMATH Keywords

growing context-sensitive languagegrowing context-sensitive grammar

Mathematics Subject Classification ID

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