文献

J-GLOBAL ID：202002286576935018   整理番号：20A2654827

グラフ歩行オートマトンにおける計算の可逆性【JST・京大機械翻訳】

Reversibility of computations in graph-walking automata

著者 (2件)： Kunc Michal (Department of Mathematics and Statistics, Masaryk University, Kotlarska 2, Brno 611 37, Czech Republic) ,  Okhotin Alexander (Department of Mathematics and Computer Science, St. Petersburg State University, 14th Line V.O., 29, Saint Petersburg 199178, Russia)
資料名： Information and Computation  (Information and Computation)
巻： 275  ページ： Null  発行年： 2020年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフ歩行オートマトン(GWA)は,エッジに従って入力として与えられたグラフを横断する有限状態デバイスである。それらを理論的概念として,またロボット工学における経路発見のモデルとして研究した。グラフが特定の抽象機械のメモリ構成の集合と見なされるならば,次に,装置の様々なファミリーは,GWAとして記述することができる:例えば,2方向有限オートマトン,それらのマルチヘッドとマルチテープバリアント,ツリー歩行オートマトン,およびペブル,画像歩行オートマトン,空間結合Turingマシンなどのそれらの拡張。本論文では,任意の決定論的GWAの可逆GWAへの変換を定義した。これは,一定因子が横断されるグラフの程度に依存する状態数における線形ブローアップで行われる。建設は,GWAとして表現可能なすべての基本モデルに直接適用し,特に,個々のモデルを作成するための多数の既存の結果を,あらゆる入力で停止する。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 記憶装置 ,  *オートマトン ,  Turing機械 ,  有限オートマトン ,  線形性 ,  可逆性
準シソーラス用語： ロボット工学 ,  決定論 ,  マルチヘッド , 【Automatic Indexing@JST】

著者キーワード (5件)： グラフ歩行オートマトン ,  木歩行オートマトン ,  有限オートマトン ,  可逆計算 ,  ハルティング

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

タイトルに関連する用語 (5件)： グラフ ,  歩行 ,  オートマトン ,  計算 ,  可逆性