文献

J-GLOBAL ID：201802254834451885   整理番号：18A1853549

可逆セルラオートマトン:基本的古典的研究結果から最近の成果まで

Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments

著者 (1件)： KARI Jarkko (Univ. Turku, Turku, FIN)
資料名： New Generation Computing  (New Generation Computing)
巻： 36  号： 3  ページ： 145-172  発行年： 2018年07月 
JST資料番号： Y0555A  ISSN： 0288-3635  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ・セルラオートマトンは単純で自然な構造を有しているが,その中で,RCA(Reversible Cellular Automaton)はいかなる情報も消去することなく,従って,動的に時間を遡ることが可能なオートマトンであり,本稿では,その特性を考察。
・最初に,RCAを構築する3種の手法を紹介,状態集合または状態空間を分割する手法と時間バッファリングを用いる手法。
・次いで,1次元セルラオートマトンが可逆であるかどうかを判定する効率良いアルゴリズムを提示し,同時に,高次元オートマトンに対してはそのようなアルゴリズムは存在しないことを証明。
・さらに,3つの型の普遍性,即ち,計算普遍性,固有普遍性,構築普遍性を導入。
・最後に,可逆性に加えて,さらなる制約に焦点を当て,対称性,拡張性等を議論し,保存則についても議論。

シソーラス用語： *セルラオートマトン ,  *計算量 ,  可逆性 ,  Turing機械 ,  状態遷移図 ,  遷移状態 ,  普遍性 ,  可逆変化
準シソーラス用語： 状態空間 ,  状態推移図 ,  転移状態

分類 (2件)： オートマトン理論  (JB04000O) ,  計算理論  (JB02000A)

引用文献 (56件)：

• Kari, J.: Reversible cellular automata. Developments in language theory. Lecture Notes in Computer Science, vol. 3572, pp. 57-68. Springer, Berlin (2005)
• Kari, J.: Theory of cellular automata: a survey. Theoret. Comput. Sci. 334(1-3), 3-33 (2005)
• Morita, K.: Reversible computing and cellular automata-a survey. Theoret. Comput. Sci. 395(1), 101-131 (2008)
• Morita, K.: Theory of Reversible Computing, Monographs in Theoretical Computer Science, An EATCS Series. Springer, New York (2017)
• Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical systems. Math. Syst. Theory 3(4), 320-375 (1969)

タイトルに関連する用語 (3件)： セルラオートマトン ,  研究 ,  成果