Metatheorems for decision problems on hyperedge replacement graph languages

DOI10.1007/BF00288976MaRDI QIDQ1121675zbMATH OpenOpenAlexFDO

Authors Annegret Habel, Walter Vogler, Hans-Jörg 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)

Recommendations

• Publication:3815541
• Publication:4711083
• Hyperedge replacement: grammars and languages
• Publication:4852905
• Decision problems for edge grammars

Cites work

• scientific article; zbMATH DE number 3827231 (Why is no real title available?)
• scientific article; zbMATH DE number 4035178 (Why is no real title available?)
• scientific article; zbMATH DE number 4049098 (Why is no real title available?)
• scientific article; zbMATH DE number 4049099 (Why is no real title available?)
• scientific article; zbMATH DE number 4053039 (Why is no real title available?)
• scientific article; zbMATH DE number 4060749 (Why is no real title available?)
• scientific article; zbMATH DE number 4087049 (Why is no real title available?)
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Characteristics of graph languages generated by edge replacement
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Graph theoretic closure properties of the family of boundary NLC graph languages
• 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
• Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
• Metatheorems for decision problems on hyperedge replacement graph languages
• The bounded degree problem for NLC grammars is decidable

Cited in

(16)

• Decision problems for edge grammars
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• Theoretical properties in hypergraphs
• Hyperedge replacement with rendezvous
• The complexity of connectivity problems on context-free graph languages
• scientific article; zbMATH DE number 4101136 (Why is no real title available?)
• Graph-theoretic properties compatible with graph derivations
• Metatheorems for decision problems on hyperedge replacement graph languages
• Some new decision results for edge grammars
• A comparison of compatible, finite, and inductive graph properties
• Logical description of context-free graph languages
• Separation results for separated apex NLC and NCE graph languages
• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• Acyclic Contextual Hyperedge Replacement: Decidability of Acyclicity and Generative Power
• scientific article; zbMATH DE number 177454 (Why is no real title available?)
• scientific article; zbMATH DE number 4087049 (Why is no real title available?)

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

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