文献

J-GLOBAL ID：201702289753720382   整理番号：17A1357488

max-plusオートマトンの遅延と後悔決定化について【Powered by NICT】

On delay and regret determinization of max-plus automata

著者 (5件)： Filiot Emmanuel (Universite ́ Libre de Bruxelles, Belgium) ,  Jecker Ismael (Universite ́ Libre de Bruxelles, Belgium) ,  Lhote Nathan (Universite ́ Libre de Bruxelles, Belgium) ,  Perez Guillermo A. (Universite ́ Libre de Bruxelles, Belgium) ,  Raskin Jean-Francois (Universite ́ Libre de Bruxelles, Belgium)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： LICS  ページ： 1-12  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： WA,半環上の重み付きオートマトン(ZU{-∞},max,+)のための決定問題の決定可能性は長年の未解決の問題である。決定論的WAの探索空間を制約することによってそれに接近する二つの方法を提案した:K遅延と後悔。Nの言葉でNと同じ機能を定義する決定論的オートマトンDと全単語のα存在し,α上のDの受容はαに及ぼすNの最大受容ランから離れた最もで常にすればWA NはK遅延determinizableである。すなわち,同じ長さの全てのプレフィックスに沿って,二回の重みの和の間の絶対差は高々kである言語におけるα全単語のための,その値とNによるαに割り当てられた値の間の絶対差は最もrであることをその非決定性は,フライ上で分解されたNの実行を構築することができるかどうかWA NがR後悔determinizableWAすれば,いくつかのkのk遅延determinizableである場合にのみdeterminizableことを示した。いくつかのKの存在を決定することである一般的決定問題としてとしては困難である。k及びrは入力として与えられたとき,k遅延と後悔決定問題はEXPTIME完全であることを示した。もWAは後悔いくつかrのdeterminizableであるかどうかを決定するEXPTIMEであることを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 決定問題 ,  言語 ,  単語 ,  *オートマトン ,  非決定性
準シソーラス用語： プレフィックス ,  言葉 ,  探索空間 ,  決定論 ,  決定可能性 , 【Automatic Indexing@JST】

分類 (3件)： 計算理論  (JB02000A) ,  数理計画法  (KA03030M) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (4件)： Max ,  オートマトン ,  遅延 ,  後悔