A pumping result for 2-context-free languages

DOI10.1016/0304-3975(88)90070-9zbMath0662.68077OpenAlexW2164853718MaRDI QIDQ1114418

Kai Salomaa

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90070-9

zbMATH Keywords

schedulingcontext-free grammarsrewriting systemcontext-free languageshierarchypattern selector grammarspumping property

Mathematics Subject Classification ID

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

Related Items

Hierarchy of k-context-free languages part 1 ⋮ Hierarchy ofk-context-free languages

Cites Work

• 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 grammars with selective rewriting
• Context-free like restrictions on selective rewriting
• Manipulating derivation forests by scheduling techniques
• Closure properties of selective substitution grammars
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling Flat Graphs
• Hierarchy ofk-context-free languages