時間付き多重集合書換えの有界性と到達可能性の解析

概要

論文の詳細を見る
時間アークペトリネットと時間付きオートマトンを包含する枠組みとして,時間付き多重集合書換えを提案する.時間付き多重集合書換えは,多重集合上の書換えに時間の概念を付加したものである.多重集合の各要素にはクロックが付与されており,多重集合の変化は通常の書換えによるものだけでなく,時間の経過によるものも含む.また,書換えの条件としてクロックに関するものを含むことができる.本発表では,時間付き多重集合書換えにおける到達可能性.有界性・被覆性の解析について述べる.ある多重集合が到達可能であるとは,それが初期集合から始めて通常の書換えと時間経過を繰り返して得られるということである.ある多重集合が被覆可能であるとは,初期多重集合から与えられた多重集合を含むような多重集合に到達可能であるということである.また,多重集合書換え系が有界であるとは,到達可能な多重集合の大きさに上限があるということである.各性質が決定可能であるかどうかは,解析の対象となる時間付き多重集合書換え系が不変制約や対角線制約を含むかどうかによって違いが生じる.まず,不変制約を含む時間付き多重集合書換えについて,到達可能性・有界性・被覆性がいずれも決定不能であることを示す.次に,不変制約を含まない時間付き多重集合書換えについて,到達可能性が決定不能であること,有界性・被覆性が決定可能であることを示す.最後に,対角線制約を含む場合には,たとえ不変制約を含まない場合であっても,各性質が決定不能になることを示す.
一般社団法人情報処理学会の論文
2002-09-15

時間付き多重集合書換えの有界性と到達可能性の解析

スポンサーリンク

概要

著者

関連論文

スポンサーリンク