文献

J-GLOBAL ID：202002255891322269   整理番号：20A2581896

右一方向跳躍有限オートマトンの決定可能性【JST・京大機械翻訳】

Decidability of Right One-Way Jumping Finite Automata

著者 (2件)： Beier Simon (Institut fuer Informatik, Universitaet Giessen, Arndtstr. 2, 35392 Giessen, Germany) ,  Holzer Markus (Institut fuer Informatik, Universitaet Giessen, Arndtstr. 2, 35392 Giessen, Germany)
資料名： International Journal of Foundations of Computer Science  (International Journal of Foundations of Computer Science)
巻： 31  号： 6  ページ： 805-825  発行年： 2020年 
JST資料番号： W0409A  ISSN： 0129-0541  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 不連続情報処理のためのオートマトンモデルである,ジャンピングオートマトンのバリアントである(右)一方向ジャンプ有限オートマトン(ROWJFA)に対する,右一方向ジャンプ有限オートマトン,LNCS,2018]の,著者らの研究[S.Beier,M.Holzer]を継続する。ここでは,ROWJFAに対する決定問題に焦点を当てた。それは,例えば,優秀性,有限性,普遍性,単語問題と変種,置換の下の閉鎖,その他のような大部分の問題が,決定可能であることを見つけ出した。さらに,ROWJFA置換閉鎖言語の厳密な階層内の言語の封じ込めが,受信状態数によって,また,置換閉鎖正規または跳躍有限オートマトン言語が,ROWJFAによって受け入れられるかどうかを,また,解読できる,ことを示した。他方では,(線形)コンテキストフリー言語に対して,対応するROWJFA受容問題は不可解になることを証明した。さらに,考察した決定問題に対するいくつかの複雑性結果についても論じた。Copyright 2020 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *オートマトン ,  決定問題 ,  言語 ,  情報処理 ,  *有限オートマトン ,  受信 ,  線形性 ,  不連続性 ,  跳躍現象 ,  有限性 ,  普遍性 ,  語の問題
準シソーラス用語： 決定可能性 ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 右一方向跳躍オートマトン ,  有限オートマトンの跳躍 ,  決定問題

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

タイトルに関連する用語 (3件)： 跳躍 ,  有限オートマトン ,  決定可能性