PROGRAMMED GRAPH REPLACEMENT SYSTEMS
Andreas Schürr · WORLD SCIENTIFIC eBooks · 1997
Various forms of programmed graph replacement systems as extensions of contextsensitive graph replacement systems have been proposed until today. They differ considerably with respect to their underlying graph models, the supported forms of graph replacement rules, and offered rule regulation mechanisms. Some of them have additional constructs for the definition of graph schemata, derived graph properties, and so forth. It is rather difficult to develop precise and compact descriptions of programmed graph replacement systems, a necessary prerequisite for any attempt to compare their properties in detail. Programmed Logic-based Structure Replacement (PLSR) systems are a kind of intermediate definition language for this purpose. They treat specific graph classes as sets of predicate logic formulas with certain properties, so-called structures. Their rules preserve the consistency of manipulated structures and use nonmonotonic reasoning for checking needed preand postconditions. So-called Basic Control Flow (BCF) expressions together with an underlying fixpoint theory provide needed means for programming with rules. This chapter introduces first the basic framework of PLSR systems and studies afterwards the essential properties of context-sensitive graph replacement approaches themselves as well as popular rule regulation mechanisms.