文献

J-GLOBAL ID：201802258632470313   整理番号：18A0266348

定量的公平シミュレーションゲーム【Powered by NICT】

Quantitative fair simulation games

著者 (5件)： Chatterjee Krishnendu (IST, Austria) ,  Henzinger Thomas A. (IST, Austria) ,  Otop Jan (IST, Austria) ,  Otop Jan (University of Wroclaw, Poland) ,  Velner Yaron (Tel Aviv University, Israel)
資料名： Information and Computation  (Information and Computation)
巻： 254  号： P2  ページ： 143-166  発行年： 2017年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 言語介在物のアンダ近似であるが,はるかに低い計算量を持つとしてのシミュレーションはオートマトンのための言語包含に魅力的な代替法である。シミュレーションも特定セット無限運転のシミュレーションのための,すなわち,(1)公平なシミュレーション,二つの直交方向に拡張した;および(2)定量的シミュレーション,重み付きオートマトン間のシミュレーション。PSPACE完全公平な微量包有物が,多項式時間で計算できる公平なシミュレーション。重み付きオートマトンに対して,(定量的)言語介在物問題は一般に決定不能であるが,(定量的)シミュレーションは,定量的ゲーム,疑似多項式時間アルゴリズムを認めるに減少した。Buechi条件を持つ重み付きオートマトンのための(定量的)シミュレーションを研究し,すなわち,重みオートマトン重み付きオートマトンの公平なシミュレーションを一般化した。重み付きオートマトンにBuechi受容条件を課すシミュレーションゲームの多くの基本的な特性を変化させることを示し,それらはまだ疑似多項式時間アルゴリズムを許容する。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 計算量 ,  *シミュレーション ,  介在物 ,  言語 ,  直交性 ,  オートマトン ,  近似法 ,  *ゲーム ,  包有物
準シソーラス用語： 多項式時間アルゴリズム ,  多項式時間 ,  *シミュレーションゲーム , 【Automatic Indexing@JST】

著者キーワード (5件)： シミュレーション ,  公平なシミュレーション ,  定量的シミュレーション ,  重み付きオートマトン ,  平均-ペイオフと割引和ゲーム

分類 (2件)： 計算理論  (JB02000A) ,  オートマトン理論  (JB04000O)

タイトルに関連する用語 (2件)： 定量 ,  シミュレーションゲーム