Manipulating derivation forests by scheduling techniques

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

zbMATH Keywords

pumpingmembership problemsNParbitrary grammarsgeneralization of context-free rewritingk-parallel rewritingmembership complexitynonpropagating grammarspolynomial dynamic programming membership algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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