文献

J-GLOBAL ID：201802250906991525   整理番号：18A0331567

一方可逆マルチヘッド有限オートマトン【Powered by NICT】

One-way reversible multi-head finite automata

著者 (2件)： Kutrib Martin (Institut fuer Informatik, Universitaet Giessen, Arndtstr. 2, 35392 Giessen, Germany) ,  Malcher Andreas (Institut fuer Informatik, Universitaet Giessen, Arndtstr. 2, 35392 Giessen, Germany)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 682  ページ： 149-164  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 一方向マルチヘッド有限オートマトンは可逆計算を実行する能力に向けて考察した。ヘッドのk≧1数では,一方向kヘッド有限オートマタによってではなく,任意の一方向可逆Kヘッド有限オートマトンにより解くことができる問題であることを示した。さらに,一方向可逆マルチヘッド有限オートマトンのための得られた適切なヘッド階層。閉包特性と決定可能性問題を調べた。二頭を持つワンウエイ可逆有限オートマトンはまだ強力なモデルことが分かった,ほとんどすべての一般的に研究された問題はsemidecidableもないからである。最後に,記述量の側面を検討し,非再帰的トレードオフを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 計算 ,  閉包 ,  *有限オートマトン
準シソーラス用語： 決定可能性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 一方マルチヘッド有限オートマトン ,  可逆計算 ,  決定可能性問題

分類 (2件)： 人工知能  (JE08000Z) ,  オートマトン理論  (JB04000O)

タイトルに関連する用語 (2件)： マルチヘッド ,  有限オートマトン