A comparison of compatible, finite, and inductive graph properties

1993

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.