On the complexity of formal grammars

DOI10.1007/BF00289076zbMath0357.68050OpenAlexW2017143384MaRDI QIDQ1239000

Ronald V. Book

Publication date: 1978

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289076

Mathematics Subject Classification ID

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

Related Items

Growing context-sensitive languages and Church-Rosser languages ⋮ On weak growing context-sensitive grammars ⋮ Sweeping input-driven pushdown automata ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ On growing context-sensitive languages ⋮ The ancestor width of grammars and languages ⋮ Manipulating derivation forests by scheduling techniques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The membership question for ETOL-languages is polynomially complete
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• Comparing complexity classes
• Checking automata and one-way stack languages
• Time-bounded grammars and their languages
• On the extension of Gladkij's theorem and the hierarchies of languages
• Some restrictions onW-grammars
• Classes of languages and linear-bounded automata
• The complexity of theorem-proving procedures
• On the structure of context-sensitive grammars
• Three theorems on phrase structure grammars of type 1