Pattern selector grammars and several parsing algorithms in the context- free style
From MaRDI portal
Publication:1081314
DOI10.1016/0022-0000(85)90046-7zbMath0601.68057OpenAlexW1965321646MaRDI QIDQ1081314
Publication date: 1985
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(85)90046-7
context-free languagescomplexity of the membership problemNP time bound for parsingpolynomial bound on the shortest derivation
Related Items
Applications of scheduling theory to formal language theory ⋮ Concerning two-adjacent context-free languages ⋮ On the Kleijn-Rozenberg k-adjacent languages ⋮ A pumping result for 2-context-free languages ⋮ Hierarchy of k-context-free languages part 1 ⋮ Hierarchy ofk-context-free languages ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ Manipulating derivation forests by scheduling techniques
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Applications of scheduling theory to formal language theory
- Context-free like restrictions on selective rewriting
- The membership question for ETOL-languages is polynomially complete
- General context-free recognition in less than cubic time
- The tape-complexity of context-independent developmental languages
- The Complexity of Languages Generated by Attribute Grammars
- Time and space complexity of inside-out macro languages
- Recognition of deterministic ETOL languages in logarithmic space
- On the Tape Complexity of Deterministic Context-Free Languages
- The complexity of the membership problem for some extensions of context-free languagest†
- Recognition and parsing of context-free languages in time n3