状態を伴うアフィンベクトル付加システムにおける可到達性の複雑性【JST・京大機械翻訳】

Blondin Michael; Raskin Mikhail

プレプリント

J-GLOBAL ID：202202200475240344 整理番号：21P0016639

状態を伴うアフィンベクトル付加システムにおける可到達性の複雑性【JST・京大機械翻訳】

The Complexity of Reachability in Affine Vector Addition Systems with States

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2019年09月05日プレプリントサーバーでの情報更新日： 2021年07月19日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

状態(VASS)によるベクトル付加システムは,同時システムの形式的検証のために広く使われている。それらの大きな計算の複雑さを考えると,実用的アプローチは,例えば負の中間対値を可能にするような到達性緩和のような技術に依存している。典型的には,非可解性に翻訳するプリミティブを豊富に含むVASSの実現可能性を疑問視する。この懸念により,アフィン演算の任意のクラスに関して,整数緩和の複雑性を指摘した。より具体的には,アフィン演算(アフィンVASS)で拡張されたVASSにおける整数到達可能性の複雑性に関するトリコテージョンを提供する。すなわち,著者らは,リセットによるVASS,(擬似)転送によるVASSのためのPSPACE完全,および(擬似)コピーによるVASSのためのNP完全であり,また,他のクラスに対して不可解であることを示した。さらに,アフィンVASSにおける標準可到達性のための二分法を提示する:それは,置換によるVASSに対して決定でき,他のクラスに対して不可解である。これは,アフィンVASSにおける到達可能性の完全な統一的複雑性景観をもたらした。また,クラスよりも固定アフィンVASSによりパラメータ化された可到達性問題を考察し,この設定において複雑性景観が任意であることを示した。【JST・京大機械翻訳】

, , , , , , ,
, , , , 【Automatic Indexing@JST】

システム・制御理論一般 , システム設計・解析

, ,

前のページに戻る