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

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 1997-12-25

著者

• Akama K

  Hokkaido Univ.

• Akama Kiyoshi

  Hokkaido University

• Miyamoto Eiichi

  Hokkaido University

• SHIGETA YOSHINORI

  Department of System and Information Engineering, Hokkaido University

• AKAMA Kiyoshi

  Division of System and Information Engineering, Hokkaido University

• SHIGETA Yoshinori

  Toshiba Corporation

• MIYAMOTO Eiichi

  Division of System and Information Engineering, Hokkaido University

関連論文

• A Simple Framework for Objects That Have Classes and Substructures Based on ET Paradigm
• Applying Program Transformation to Type Inference for a Logic Language
• Electron Transport in Hole-Transport-Type Photoconductive Film
• A Specialization System for Domain Variables and Equivalent Transformation for Non-Equality Constraints
• Unreachability Proofs for β Rewriting Systems by Homomorphisms
• Common Structure of Semi-Thue Systems, Petri Nets, and Other Rewriting Systems

スポンサーリンク