Context-free graph languages of bounded degree are generated by apex graph grammars

DOI10.1007/BF01178511zbMath0818.68102MaRDI QIDQ1338891

George Leih, Linda Heyker, Joost Engelfriet

Publication date: 23 November 1994

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

zbMATH Keywords

context-free graph languagesapex graph grammars

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items (12)

Algorithmic uses of the Feferman-Vaught theorem ⋮ Logical description of context-free graph languages ⋮ A uniform approach to graph rewriting: The pullback approach ⋮ Domino treewidth ⋮ Quasi-rocking real-time pushdown automata ⋮ Concatenation of graphs ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ An elementary proof of double Greibach normal form ⋮ Finite graph automata for linear and boundary graph languages ⋮ Node rewriting in graphs and hypergraphs: A categorical framework ⋮ A Greibach normal form for context-free graph grammars ⋮ Double Greibach operator grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The bounded degree problem for NLC grammars is decidable
• Hyperedge replacement: grammars and languages
• Nonterminal separation in graph grammars
• Boundary graph grammars with dynamic edge relabeling
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Restrictions on NLC graph 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
• Linear graph grammars: Power and complexity
• Derivation-bounded languages
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Graph expressions and graph rewritings
• Efficient decision procedures for graph properties on context-free graph languages
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Finite-Turn Pushdown Automata
• Matrix Equations and Normal Forms for Context-Free Grammars
• On Greibach normal form construction

This page was built for publication: Context-free graph languages of bounded degree are generated by apex graph grammars