Pattern selector grammars and several parsing algorithms in the context- free style

DOI10.1016/0022-0000(85)90046-7zbMath0601.68057OpenAlexW1965321646MaRDI QIDQ1081314

B. George

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

zbMATH Keywords

context-free languagescomplexity of the membership problemNP time bound for parsingpolynomial bound on the shortest derivation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of compilers and interpreters (68N20)

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