The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] abstract rewriting system(1hit)

1-1hit
  • Common Structure of Semi-Thue Systems, Petri Nets, and Other Rewriting Systems

    Kiyoshi AKAMA  Yoshinori SHIGETA  Eiichi MIYAMOTO  

     
    PAPER-Automata,Languages and Theory of Computing

      Vol:
    E80-D No:12
      Page(s):
    1141-1148

    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 "substitutions," "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 relating 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 the concept of "places". This has been solved here by employment of the concept of contexts rather than by formalization of places. Places determine subobjects from objects, while, conversely, contexts determine objects from subobjects. A class of rewriting systems, called β rewriting systems, is proposed. It is defined on axiomatically formulated base structures, called β structures, which are used to formalize the concepts of "contexts" and "replacement" common to many rewritten objects. The class of β rewriting systems includes very important systems such as semi-Thue systems and Petri Nets. Abstract rewriting systems are also a subclass of β rewriting systems.