| Title: | OS12-2 Necessary spaces for seven-way four-dimensional Turing machines to simulate four-dimensional one-marker automata |
|---|---|
| Publication: | ICAROB2016 |
| Volume: | 21 |
| Pages: | 345-348 |
| ISSN: | 2188-7829 |
| DOI: | 10.5954/ICAROB.2016.OS12-2 |
| Author(s): | Makoto Nagatomo, Shinnosuke Yano, Makoto Sakamoto, Satoshi Ikeda, Hiroshi Furutani, Takao Ito, Tsutomu Ito, Yasuo Uchida, Tsunehiro Yoshinaga |
| Publication Date: | January 29, 2016 |
| Keywords: | computational complexity, finite automaton, lower bounds, marker, simulation, Turing machine |
| Abstract: | We think that recently, due to the advances in many application areas such as motion image processing, computer animation, and so on, it is very useful for analyzing computational complexity of multi-dimensional information processing to explicate the properties of four-dimensional automata, i.e., three-dimensional automata with the time axis. As far as we know, there is no investigation about four-dimensional automata. Then, in 2002, we first introduced four-dimensional finite automata in the world. In 2003, we investigated four-dimensional alternating Turing machines. In 2015, we show the sufficient spaces for four-dimensional Turing machines to simulate four-dimensional onemarker automata. In this paper, we continue the investigations, and deal with the necessary spaces for fourdimensional Turing machines to simulate four-dimensional one-marker automata. |
| PDF File: | https://alife-robotics.co.jp/members2016/icarob/data/papers/OS/OS12-2.pdf |
| Copyright: | © The authors. This article is distributed under the terms of the Creative Commons Attribution License 4.0, which permits non-commercial use, distribution and reproduction in any medium, provided the original work is properly cited. See for details: https://creativecommons.org/licenses/by-nc/4.0/ |
(c)2008 Copyright The Regents of ALife Robotics Corporation Ltd. All Rights Reserved.