Manipulating derivation forests by scheduling techniques
From MaRDI portal
Publication:1820586
DOI10.1016/0304-3975(86)90042-3zbMath0615.68052OpenAlexW1973852854MaRDI QIDQ1820586
Jakob Gonczarowski, Manfred K. Warmuth
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
pumpingmembership problemsNParbitrary grammarsgeneralization of context-free rewritingk-parallel rewritingmembership complexitynonpropagating grammarspolynomial dynamic programming membership algorithm
Related Items (5)
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 ⋮ Membership for growing context-sensitive grammars is polynomial
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Manipulating derivation forests by scheduling techniques