6533b7cffe1ef96bd125870c
RESEARCH PRODUCT
A comparison of compatible, finite, and inductive graph properties
Annegret HabelHans-jörg KreowskiClemens Lautemannsubject
Discrete mathematicsGeneral Computer ScienceVoltage graphDirected graphDecidabilityTheoretical Computer ScienceCombinatoricsVertex-transitive graphRule-based machine translationClique-widthGraph propertyNull graphMathematicsComputer Science(all)description
Abstract In the theory of hyperedge-replacement grammars and languages, one encounters three types of graph properties that play an important role in proving decidability and structural results. The three types are called compatible, finite, and inductive graph properties. All three of them cover graph properties that are well-behaved with respect to certain operations on hypergraphs. In this paper, we show that the three notions are essentially equivalent. Consequently, three lines of investigation in the theory of hyperedge replacement - so far separated - merge into one.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1993-03-01 | Theoretical Computer Science |