Metatheorems for decision problems on hyperedge replacement graph languages

DOI10.1007/BF00288976zbMath0674.68047OpenAlexW2068755149MaRDI QIDQ1121675

Walter Vogler, Annegret Habel, Hans-Joerg Kreowski

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1007/bf00288976

zbMATH Keywords

graph grammarsgraph languageshyperedge replacement

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

The complexity of connectivity problems on context-free graph languages ⋮ Hyperedge replacement with rendezvous ⋮ Metatheorems for decision problems on hyperedge replacement graph languages ⋮ Logical description of context-free graph languages ⋮ Decision problems for edge grammars ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ Separation results for separated apex NLC and NCE graph languages ⋮ Unnamed Item ⋮ A comparison of compatible, finite, and inductive graph properties

Cites Work

• The bounded degree problem for NLC grammars is decidable
• Graph theoretic closure properties of the family of boundary NLC graph languages
• Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
• Characteristics of graph languages generated by edge replacement
• Metatheorems for decision problems on hyperedge replacement graph languages
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
• Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Metatheorems for decision problems on hyperedge replacement graph languages