Applications of scheduling theory to formal language theory

DOI10.1016/0304-3975(85)90092-1zbMath0602.68058OpenAlexW2012508246MaRDI QIDQ1082085

Manfred K. Warmuth, Jakob Gonczarowski

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90092-1

zbMATH Keywords

computational complexityContext-free grammarscontext-free rewritingdynamic programming membership algorithmsE0L rewritingNP- hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

Pattern selector grammars and several parsing algorithms in the context- free style ⋮ Concerning two-adjacent context-free 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
• On the generative power of regular pattern grammars
• Pattern selector grammars and several parsing algorithms in the context- free style
• Concerning two-adjacent context-free languages
• Context-free like restrictions on selective rewriting
• The membership question for ETOL-languages is polynomially complete
• NP-complete scheduling problems
• Manipulating derivation forests by scheduling techniques
• Optimal scheduling for two-processor systems
• Scheduling precedence graphs of bounded height
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling Interval-Ordered Tasks
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Complexity of Scheduling under Precedence Constraints
• Scheduling Opposing Forests
• Recognition and parsing of context-free languages in time n3
• An efficient context-free parsing algorithm
• Erratum “Optimal Sequencing of Two Equivalent Processors”

This page was built for publication: Applications of scheduling theory to formal language theory