Double Greibach operator grammars

DOI10.1016/S0304-3975(99)00138-3zbMath0952.68074OpenAlexW2090256263MaRDI QIDQ1589438

R. Smith

Publication date: 12 December 2000

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00138-3

zbMATH Keywords

normal formscontext-free grammarsformal languageshierarchydecision properties

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

Quasi-rocking real-time pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boundary graph grammars with dynamic edge relabeling
• Apex graph grammars and attribute grammars
• An elementary proof of double Greibach normal form
• Separating \(k\)-separated eNCE graph languages
• Context-free graph languages of bounded degree are generated by apex graph grammars
• A hierarchy of eNCE families of graph languages
• Linear graph grammars: Power and complexity
• Node replacement graph languages squeezed with chains, trees, and forests
• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• Handle-rewriting hypergraph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• On Equivalence and Containment Problems for Formal Languages
• Syntactic Analysis and Operator Precedence
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Matrix Equations and Normal Forms for Context-Free Grammars
• On Greibach normal form construction
• Efficient recognition algorithms for boundary and linear eNCE graph languages

This page was built for publication: Double Greibach operator grammars