In: IEICE Trans. on Information Systems, Vol. E80-D, No. 12, pages 1141-1148. 1998.
Abstract: Many rewriting systems, including those of terms, strings, graphs, and conjunction of atoms, are used throughout computer science and artificial intelligence. While the concepts of `substitution', `places' in objects and the `replacement' of `subobjects' by other objects seems to be common to all rewriting systems, there does not exist a common foundation for such systems. At the present time, many of the theories are constructed independently, one for each kind of rewritten object. In the conventional approach, abstract rewriting systems are used to discuss common properties of all rewriting systems. However, they are too abstract to capture properties related to substructures of objects. This paper aims to provide a first step towards a unified formalization of rewriting systems. The major problem in their formulation may be the formalization of places. Places determine subobjects from objects, while, conversely, contexts determine objects from subobjects. A class of rewriting systems, called beta rewriting systems, is proposed. It is defined on axiomatically formulated base structures, called beta structures, which are used to formalize the concepts of `contexts' and `replacement' common to many rewritten objects. The class of beta rewriting systems includes very important systems such as semi-Thue systems and Petri nets. Abstract rewriting systems are also a subclass of beta rewriting systems.
Keywords: Petri nets, rewriting systems, semi-Thue systems.