Metatheorems for decision problems on hyperedge replacement graph languages
If a graph-theoretical property is compatible with the derivation process of hyperedge replacement graph grammars in a certain way, the property turns out to be decidable for the corresponding graph languages. More exactly speaking, we consider two questions: (1) Is there a graph in the generated language having the property? (2) Do all graphs in the generated language have the property? In both cases, we get decidability for all hyperedge replacement graph grammars as inputs. Colorability, Hamiltonicity, and planarity are shown to be compatible so that our decidability results apply to them.
- 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
- 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?)
- Metatheorems for decision problems on hyperedge replacement graph languages
- The bounded degree problem for NLC grammars is decidable
- Metatheorems for decision problems on hyperedge replacement graph languages
- The complexity of connectivity problems on context-free graph languages
- Logical description of context-free graph languages
- A comparison of compatible, finite, and inductive graph properties
- HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
- Theoretical properties in hypergraphs
- scientific article; zbMATH DE number 4087049 (Why is no real title available?)
- scientific article; zbMATH DE number 4101136 (Why is no real title available?)
- scientific article; zbMATH DE number 177454 (Why is no real title available?)
- scientific article; zbMATH DE number 965 (Why is no real title available?)
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- Hyperedge replacement with rendezvous
- Decision problems for edge grammars
- Some new decision results for edge grammars
- Separation results for separated apex NLC and NCE graph languages
- Graph-theoretic properties compatible with graph derivations
- Acyclic Contextual Hyperedge Replacement: Decidability of Acyclicity and Generative Power
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)
