文献

J-GLOBAL ID：202202274669805125   整理番号：22A1053048

Mod2多重度オートマトンを用いた無限語の正規言語の表現【JST・京大機械翻訳】

Representing Regular Languages of Infinite Words Using Mod 2 Multiplicity Automata

著者 (4件)： Angluin Dana (Yale University, New Haven, CT, USA) ,  Antonopoulos Timos (Yale University, New Haven, CT, USA) ,  Fisman Dana (Ben-Gurion University, Beer-Sheva, Israel) ,  George Nevin (Yale University, New Haven, CT, USA)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 13242  ページ： 1-20  発行年： 2022年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 無限単語の正規言語に対する表現として,モッド2多重オートマトン(M2MA)の適合性を検討した。M2MAは,多くの他の表現とは対照的に,メンバーシップと等価クエリを持つ多項式時間で学習できることが知られている決定論的表現である。非決定論的オートマトンと比較して,M2MAのもう一つの利点は,それらの等価性が多項式時間で決定でき,相補性が付加定数サイズ増加だけを招くことである。学習時間は表現のサイズによってパラメータ化されるので,特に,代替表現の相対的簡潔性,特に,タイプ:決定論的,非決定論的,および強いあいまい性,のLTL公式およびBuechiオートマトンに,特別な注意を払った。最悪ケースの上部と下限の理論的結果を,ランダムに生成されたオートマトンとLTL公式の特定のファミリーに対して計算した実験結果で補足した。Copyright The Author(s) 2022 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *オートマトン ,  *言語 ,  適応性 ,  *多重化 ,  多重度 ,  相補性 ,  等価性 ,  曖昧さ ,  単語 ,  パラメタリゼーション
準シソーラス用語： *正規言語 ,  多項式時間 ,  クエリー ,  決定論 ,  線形時間論理 , 【Automatic Indexing@JST】

著者キーワード (5件)： 多重度オートマトン ,  正規オメガ言語 ,  Buechiオートマトン ,  線形時間論理 ,  簡潔性

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

タイトルに関連する用語 (5件)： 多重度 ,  オートマトン ,  無限 ,  正規言語 ,  表現