A Greibach normal form for context-free graph grammars

DOI10.1007/3-540-55719-9_70zbMath1425.68162OpenAlexW2152195025MaRDI QIDQ5204313

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)

Related Items (6)

Hypergraph Basic Categorial Grammars ⋮ Unnamed Item ⋮ Abstracting Complex Data Structures by Hyperedge Replacement ⋮ An elementary proof of double Greibach normal form ⋮ Juggrnaut: using graph grammars for abstracting unbounded heap structures ⋮ Hypergraph languages of bounded degree

Cites Work

• Hyperedge replacement: grammars and languages
• Nonterminal separation in graph grammars
• Boundary graph grammars with dynamic edge relabeling
• The complexity of finding uniform emulations on paths and ring networks
• A comparison of boundary graph grammars and context-free hypergraph grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• The string generating power of context-free hypergraph grammars
• Context-free hypergraph grammars have the same term-generating power as attribute grammars
• Hypergraph languages of bounded degree
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Linear graph grammars: Power and complexity
• Derivation-bounded languages
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph expressions and graph rewritings
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Matrix Equations and Normal Forms for Context-Free 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: A Greibach normal form for context-free graph grammars