scientific article; zbMATH DE number 4087049
The paper under review is a very short discussion of the following problem: Given a graph property Q and a class of graph grammars, does Q hold for all (resp.: for some) graphs generated by a grammar of this class? The authors restrict the notion of graph grammar to the hyperedge replacement systems. In this case, it can be shown that both versions of the problem are decidable if Q is (in some sense) compatible with the derivation process. Colorability, connectivity, cycle freeness, planarity, and the existence of Hamiltonian and Eulerian paths are some examples of compatible properties. The paper is clearly written, but it does not contain any proofs. The interested reader can find some of them in the first author's WG 88 paper [Graph-theoretic properties compatible with graph derivations, Lect. Notes Comput. Sci. 344, 11-29 (1989)].
- Metatheorems for decision problems on hyperedge replacement graph languages
- Algorithms for graph problems on BNLC structured garphs
- scientific article; zbMATH DE number 4160146 (Why is no real title available?)
- scientific article; zbMATH DE number 4060749 (Why is no real title available?)
- Tree automata, tree decomposition and hyperedge replacement
- Recognizing edge replacement graph languages in cubic time
- Filtering hyperedge-replacement languages through compatible properties
- scientific article; zbMATH DE number 965 (Why is no real title available?)
- Decision problems for edge grammars
- Some new decision results for edge grammars
- Graph-theoretic properties compatible with graph derivations
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815541)