A Greibach normal form for context-free graph grammars

DOI10.1007/3-540-55719-9_70MaRDI QIDQ5204313zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet

Publication date 4 December 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55719-9_70

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Context-free graph languages of bounded degree are generated by apex graph grammars
• scientific article; zbMATH DE number 2201369
• Normal forms for context-free node-rewriting hypergraph grammars
• Greibach normal form transformation revisited.
• scientific article; zbMATH DE number 5842462

Cites work

• A comparison of boundary graph grammars and context-free hypergraph grammars
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• Boundary graph grammars with dynamic edge relabeling
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• Derivation-bounded languages
• Graph expressions and graph rewritings
• scientific article; zbMATH DE number 4035178 (Why is no real title available?)
• scientific article; zbMATH DE number 4049099 (Why is no real title available?)
• scientific article; zbMATH DE number 4051027 (Why is no real title available?)
• scientific article; zbMATH DE number 4053039 (Why is no real title available?)
• scientific article; zbMATH DE number 4060748 (Why is no real title available?)
• scientific article; zbMATH DE number 4060749 (Why is no real title available?)
• scientific article; zbMATH DE number 4106286 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 17539 (Why is no real title available?)
• scientific article; zbMATH DE number 177419 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 219258 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• Hypergraph languages of bounded degree
• Linear graph grammars: Power and complexity
• Matrix Equations and Normal Forms for Context-Free Grammars
• Nonterminal separation in graph grammars
• The complexity of finding uniform emulations on paths and ring networks
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The string generating power of context-free hypergraph grammars

Cited in

(13)

• An elementary proof of double Greibach normal form
• Hypergraph languages of bounded degree
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Double Greibach operator grammars
• A Local Greibach Normal Form for Hyperedge Replacement Grammars
• The normal form of lattice-valued context free grammars
• Normal forms for context-free node-rewriting hypergraph grammars
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• Abstracting Complex Data Structures by Hyperedge Replacement
• scientific article; zbMATH DE number 4064512 (Why is no real title available?)
• scientific article; zbMATH DE number 7456053 (Why is no real title available?)
• Hypergraph basic categorial grammars
• Juggrnaut: using graph grammars for abstracting unbounded heap structures

This page was built for publication: A Greibach normal form for context-free graph grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204313)