Complexity metatheorems for context-free grammar problems

DOI10.1016/S0022-0000(76)80044-XzbMath0377.68038MaRDI QIDQ1246270

Thomas G. Szymanski, Harry B. III Hunt

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

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

Related Items

Suffix languages in Lr parsing ⋮ Boundedly \(\text{LR}(k)\)-conflictable grammars

Cites Work

• LR-regular grammars - an extension of LR(k) grammars
• On the complexity of LR(k) testing
• Noncanonical Extensions of Bottom-Up Parsing Techniques
• Computational Parallels between the Regular and Context-Free Languages
• Corrigendum: `` Lower Bounds and Reductions Between Grammar Problems
• A note on undecidable properties of formal languages
• A helpful result for proving inherent ambiguity
• An Overview of the Theory of Computational Complexity
• On the translation of languages from left to right
• Unnamed Item
• Unnamed Item