文献

J-GLOBAL ID：202202288988531106   整理番号：22A0326973

有界曖昧性の確率的オートマトン【JST・京大機械翻訳】

Probabilistic automata of bounded ambiguity

著者 (5件)： Fijalkow Nathanaeel (CNRS, LaBRI, France) ,  Fijalkow Nathanaeel (The Alan Turing Institute of data science, London, United Kingdom of Great Britain and Northern Ireland) ,  Riveros Cristian (Pontificia Universidad Catolica de Chile, Chile) ,  Riveros Cristian (Millennium Institute for Foundational Research on Data (IMFD), Chile) ,  Worrell James (University of Oxford, United Kingdom of Great Britain and Northern Ireland)
資料名： Information and Computation  (Information and Computation)
巻： 282  ページ： Null  発行年： 2022年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 確率的オートマトンは,遷移が確率で注釈される非決定論的有限オートマトンの拡張である。その単純さにもかかわらず,このモデルは非常に表現的であり,多くのアルゴリズム的疑問は不可解である。本研究では,与えられた確率的オートマトンが与えられた閾値より大きい確率でいくつかの単語を受け入れるかどうかを問う, emしさ問題(およびその変形値問題)に焦点を当てた。有限あいまい確率オートマトンを考察した。著者らの主な貢献は,確率的経路問題と呼ばれる多目的最適化問題への縮小を通して,有限にあいまいな確率的オートマトンを解析するための効率的なアルゴリズムを構築することである。固定多義性の確率的オートマトンの値を近似するための多項式時間アルゴリズム,および2つのあいまいな確率的オートマトンのための優秀性問題のための準多項式時間アルゴリズムを得る。筆者らは,有限曖昧確率オートマトンの値がP=NPで近似できないという近似性の結果によって,これらの肯定的結果を補完する。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  閾値 ,  *オートマトン ,  順路問題 ,  確率オートマトン ,  有限オートマトン ,  多義性 ,  多目的計画法 ,  類似性 ,  曖昧さ ,  単語
準シソーラス用語： 多目的最適化 ,  多項式時間アルゴリズム ,  *有界 , 【Automatic Indexing@JST】

著者キーワード (3件)： 確率的オートマトン ,  重み付きオートマトン ,  多目的最適化

分類 (1件)： オートマトン理論  (JB04000O)

タイトルに関連する用語 (4件)： 有界 ,  曖昧性 ,  確率 ,  オートマトン