抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
著者らは,環境が強い遷移公平性仮定によって制約される,ω正規の勝利条件を有するグラフ上の2層ゲームのための不動点アルゴリズムを考察した。強い遷移公平性は,強い公平性の広く発生する特殊ケースであり,任意の実行は,特定のライブエッジの特定のセットに関してかなり公正であり,一方,ライブエッジのソース頂点が,プレイに沿って無限にしばしば訪れたとき,エッジ自体は,同様に,しばしば,プレイに沿って無限に横断される。驚いたことに,強い遷移公平性は,ω正規ゲームのための不動点アルゴリズムのアルゴリズム特性を保持し,新しいアルゴリズムは古典的アルゴリズムと同じ交替深さを持つが,新型の先行演算子を呼び出すことを示した。k対を有するRabinゲームのために,新しいアルゴリズムの複雑性はO(n ̄k+2k!)記号的ステップであり,それは強い遷移公平性推定における生エッジの数に無関係である。さらに,強い遷移公平性仮定を有するGR(1)仕様を,通常のアルゴリズムと同じように,3ネステッド不動点アルゴリズムで解くことができることを示した。対照的に,強い公平性は,公平性仮定の数に依存して,交替深さの増加を必要とする。O(n ̄k+2k!)記号ステップで走る確率的ω正規ゲームにおける定性的勝利のための直接記号アルゴリズムと同様に,強い遷移公平性仮定の下で(一般化された)Rabin,パリティ,およびGR(1)目的のための記号アルゴリズムを得て,最先端状態を改善した。最後に,このアルゴリズムに基づくBDDベースの合成エンジンを実行した。著者らは,著者らのアルゴリズムがスケーラブルで,並列化可能で,以前のアルゴリズムを桁オーダーで凌駕する一連の合成および実際のベンチマークを示した。【JST・京大機械翻訳】
