文献

J-GLOBAL ID：202202266148106643   整理番号：22A0310885

小さなアルファベット上の2方向決定論的有限オートマトンの決定論的一方向シミュレーション【JST・京大機械翻訳】

Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets

著者 (2件)： Geffert Viliam (Department of Computer Science, P. J. Safarik University, Kosice, Slovakia) ,  Okhotin Alexander (Department of Mathematics and Computer Science, St. Petersburg State University, Saint Petersburg, Russia)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 13037  ページ： 26-37  発行年： 2022年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： アルファベット[数式:原文を参照]上のn状態を有する二方向決定論的有限オートマトン(2DFA)を,[数式:原文を参照]状態を有する等価一方向オートマトン(1DFA)に変換でき,そこでは,[数式:原文を参照]を,[数式:原文を参照]で変換できることを示した。これは,メモリにおける最後の処理シンボルを維持することにより,シミュレーション1DFAは,2DFAが,最後の処理シンボルから左に移動しているいくつかの[数式:原文を参照]状態を,このシンボルから右に移動するいくつかの他のk状態へ移動させる機能と共に,今までに,最初に,事前フィックス読出を行うという状態だけを記憶することが必要であるという事実を反映している。これは,これまで,プレフィックス読み出し上の2DFAの挙動を記述する関数の数を低減する。[数式:原文を参照]状態の密接な下限を5-シンボルアルファベットを用いて確立した。スイーピングまたは方向決定2DFAを1DFAに変換する複雑性は,正確に[数式:原文を参照]であることを示した。Copyright IFIP International Federation for Information Processing 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 記憶装置 ,  *シミュレーション ,  *オートマトン ,  *有限オートマトン ,  決定
準シソーラス用語： プレフィックス ,  複雑性 ,  *決定論 ,  読出し , 【Automatic Indexing@JST】

著者キーワード (3件)： 有限オートマトン ,  2方向オートマトン ,  状態の複雑さ

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

タイトルに関連する用語 (4件)： アルファベット ,  2方向 ,  有限オートマトン ,  シミュレーション