可達集合が半線形集合であるペトリネットのアンフォールデイング  [in Japanese] Unfolding of Petri nets with semi-linear reachability set  [in Japanese]

Search this Article

Author(s)

    • 太田 淳 OHTA Atsushi
    • 愛知県立大学情報科学部 Faculty of Information Science and Technology, Aichi Prefectural University
    • 辻 孝吉 TSUJI Kohkichi
    • 愛知県立大学情報科学部 Faculty of Information Science and Technology, Aichi Prefectural University

Abstract

ペトリネットはコンカレントシステムのモデルの一つである。一般に、ペトリネットの状態数は無限であり、たとえそれが有限であったとしても、ペトリネットの規模に対して、その状態数は指数関数的に増大する。この状態空間爆発はペトリネットの解析問題を解くための大きな障害となっている。ペトリネットが有界である場合に、状態空間をコンパクトに表現する方法として、アンフォールディングが提案されている。非有界なペトリネットに対しては、被覆木生成法の考えをアンフォールディングへ適用し、ωを用いてアンフォールディングを生成する方法が提案されている。この方法は,ωを用いることから、状態空間の一部の情報が欠落する。一方、非有界なペトリネットの状態空間Rが半線形集合である場合に、拡張された被覆木を用いて,状態空間を情報欠落なしに表現する方法が提案されている。本報告では、状態空間Rが半線形集合であるペトリネットのアンフォールディング生成方法を提案する.

Petri net is an efficient model for concurrent systems. State space of a general Petri net is infinite. Even if it is finite, its size grows expornentially as the size of the net does. This problem, called state space explosion, makes Petri net analysis hard. Unfolding is suggested to give a compact description of the state space of a bounded Petri net. This is extended to unbounded net using ω borrowed from the coverability tree generating algorithm. However, using ω causes lack of information. On the other hand, if unbounded Petri net has a semilinear state space, it can be expressed without lack of information with extended coverability tree. This report suggests an extension of unfolding of Petri net with semilinear state space without lack of information.

Journal

  • Technical report of IEICE. CST

    Technical report of IEICE. CST 103(105), 1-6, 2003-05-30

    The Institute of Electronics, Information and Communication Engineers

References:  4

Codes

  • NII Article ID (NAID)
    110003299885
  • NII NACSIS-CAT ID (NCID)
    AN10438446
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    6645346
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top