分割精密化によるバイシミュレーションのための下界【JST・京大機械翻訳】

Groote Jan Friso; Martens Jan; de Vink Erik. P.

プレプリント

J-GLOBAL ID：202202219382591620 整理番号：22P0303808

分割精密化によるバイシミュレーションのための下界【JST・京大機械翻訳】

Lowerbounds for Bisimulation by Partition Refinement

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

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

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

分割精密化を使用するラベル付き遷移システムにおけるバイシミュレーションを決定する逐次および並列アルゴリズムの時間下限を提供した。逐次アルゴリズムでは,これはΩ((mmkern1mu+mkern1mu n)mkern-1mulog mkern-1mu n)であり,並列アルゴリズムでは,nは状態数であり,mは遷移の数である。下限は,決定論的遷移系のファミリー,最終的には逐次事例における2つの作用,および並列アルゴリズムに対する1つの作用によって得られる。1つの作用を有する決定論的遷移系に対して,双類似性は分割精密化よりも基本的に異なる方法で連続的に決定することができる。特に,Paige,TarjanおよびBonicは,この特定の状況に対して線形アルゴリズムを与える。オラクルの概念を利用して,このアプローチが双類似性決定のためのより高速な一般的アルゴリズムを開発するのを助けないことを示す。並列アルゴリズムでは,これらの技術が適用可能な同様の状況がある。【JST・京大機械翻訳】

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

数理計画法 , 計算理論

, ,

前のページに戻る