文献

J-GLOBAL ID：201702276702750306   整理番号：17A1357463

Petriネットにおける連続可到達性のための論理と状態をもつベクトル加算システム【Powered by NICT】

Logics for continuous reachability in Petri nets and vector addition systems with states

著者 (2件)： Blondin Michael (Technische Universitaet Muenchen, Germany) ,  Haase Christoph (University of Oxford, United Kingdom)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： LICS  ページ： 1-12  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,連続Petriネットとその拡張により定義可能な単項有理数の集合を研究した。最初に,実存FO(Q,+,<)の多項式時間決定可能フラグメントを同定し,この断片における定義可能な有理数の集合は連続Petriネットの可到達性集合と一致することを示した。次に,状態(CVASS)による連続ベクトル加算システム,計数管は,非負合理的な値を持っているかもしれないと,転移の影響は正の有理数小さいかまたは1に等しいから導出できる状態を持つベクトル加算システムを導入し,研究した。このクラスはさらに離散制御状態情報を考慮して連続Petriネットを一般化したもので厳密に導出した。CVASSの可到達性集合した実存FO(Q,+,<)から,CVASSにおける到達可能性はNP完全であることを結論できるにおける定義可能な合理的な数の集合と等価であることを証明した。最後に,著者らの結果は,最近文献で研究されてきた意思決定問題のための多項式時間アルゴリズムの数を説明し,結果として得られた。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *加算 ,  意思決定 ,  有理数 ,  *Petriネット ,  *ベクトル
準シソーラス用語： 多項式時間アルゴリズム ,  多項式時間 , 【Automatic Indexing@JST】

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： Petriネット ,  可到達性 ,  論理 ,  ベクトル ,  加算