The ancestor width of grammars and languages

DOI10.1016/S0304-3975(98)00054-1zbMath0912.68120OpenAlexW1965338147MaRDI QIDQ1274983

Franz-Josef Brandenburg

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00054-1

zbMATH Keywords

grammars and complexitynon-context-free languagesstructure of derivations

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• On the complexity of formal grammars
• Time-bounded grammars and their languages
• Non-context-free grammars generating context-free languages
• How to Make Arbitrary Grammars Look Like Context-Free Grammars
• Visits, crosses, and reversals for nondeterministic off-line machines
• Transductions of dags and trees
• The parsing for general phrase-structure grammars
• Terminal Context in Context-Sensitive Grammars
• On the structure of context-sensitive grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The ancestor width of grammars and languages