LOGIC BASED PROGRAMMED STRUCTURE REWRITING SYSTEMS

Article type: Research Article

Authors: Schürr, Andy

Affiliations: Lehrstuhl für Informatik III, RWTH Aachen, Ahornstr. 55, D-52074 Aachen, Germany. E-mail: [email protected]

Note: [] Partially supported by Netherlands Organization for Scientific Research (NWO) under grant B 62-427.

Abstract: This paper presents a new logic based framework for the formal treatment of graph rewriting systems as special cases of programmed rewriting systems for arbitrary relational structures. Considering its expressive power, the new formalism surpasses almost all variants of nonparallel algebraic as well as algorithmic graph grammar approaches by offering set-oriented pattern matching facilities as well as nonmonotonic reasoning capabilities for checking pre- and postconditions of rewrite rules. Furthermore, the formalism closes the gap between the operation-oriented manipulation of data structures by means of rewrite rules and the declaration-oriented description of data structures by means of logic based languages. Finally, the formalism even offers recursively defined (sub-)programs, by means of which the application of rewrite rules may be regulated. A denotational semantics definition for these (sub-)programs relies on a special variant of fixpoint theory for noncontinuous but monotonic functions.

DOI: 10.3233/FI-1996-263407

Journal: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 363-385, 1996