Metatheorems for decision problems on hyperedge replacement graph languages (Q1121675)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4104400
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Metatheorems for decision problems on hyperedge replacement graph languages |
scientific article; zbMATH DE number 4104400 |
Statements
Metatheorems for decision problems on hyperedge replacement graph languages (English)
0 references
1989
0 references
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.
0 references
graph languages
0 references
hyperedge replacement
0 references
graph grammars
0 references
0.8189998865127563
0 references
0.7976374626159668
0 references
