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

Kiyoshi AKAMA; Yoshinori SHIGETA; Eiichi MIYAMOTO

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

Kiyoshi AKAMA, Yoshinori SHIGETA, Eiichi MIYAMOTO

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.12 pp.1141-1148

Publication Date: 1997/12/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Automata,Languages and Theory of Computing

Cite this

Copy

Kiyoshi AKAMA, Yoshinori SHIGETA, Eiichi MIYAMOTO, "Common Structure of Semi-Thue Systems, Petri Nets, and Other Rewriting Systems" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 12, pp. 1141-1148, December 1997, doi: .
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 "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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_12_1141/_p

Copy

@ARTICLE{e80-d_12_1141,
author={Kiyoshi AKAMA, Yoshinori SHIGETA, Eiichi MIYAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Common Structure of Semi-Thue Systems, Petri Nets, and Other Rewriting Systems},
year={1997},
volume={E80-D},
number={12},
pages={1141-1148},
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 "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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Common Structure of Semi-Thue Systems, Petri Nets, and Other Rewriting Systems
T2 - IEICE TRANSACTIONS on Information
SP - 1141
EP - 1148
AU - Kiyoshi AKAMA
AU - Yoshinori SHIGETA
AU - Eiichi MIYAMOTO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 1997
AB - 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.
ER -