Manipulating derivation forests by scheduling techniques
From MaRDI portal
Publication:1820586
DOI10.1016/0304-3975(86)90042-3zbMath0615.68052MaRDI QIDQ1820586
Manfred K. Warmuth, Jakob Gonczarowski
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90042-3
pumping; membership problems; NP; arbitrary grammars; generalization of context-free rewriting; k-parallel rewriting; membership complexity; nonpropagating grammars; polynomial dynamic programming membership algorithm
Related Items
Membership for growing context-sensitive grammars is polynomial, Applications of scheduling theory to formal language theory, A pumping result for 2-context-free languages, Hierarchy of k-context-free languages part 1, Hierarchy ofk-context-free languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the generative power of regular pattern grammars
- Pattern selector grammars and several parsing algorithms in the context- free style
- Applications of scheduling theory to formal language theory
- Concerning two-adjacent context-free languages
- Context-free like restrictions on selective rewriting
- The membership question for ETOL-languages is polynomially complete
- On the complexity of formal grammars
- Scattered context grammars
- On the computational power of pushdown automata
- Closure properties of selective substitution grammars
- Profile Scheduling of Opposing Forests and Level Orders
- Scheduling Flat Graphs
- One-sided and two-sided context in formal grammars
- Recognition and parsing of context-free languages in time n3
- An efficient context-free parsing algorithm
