OS12-4 A space lower-bound technique for four-dimensional alternating Turing machines

Title:	OS12-4 A space lower-bound technique for four-dimensional alternating Turing machines
Publication:	ICAROB2016
Volume:	21
Pages:	353-356
ISSN:	2188-7829
DOI:	10.5954/ICAROB.2016.OS12-4
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:	Alternation, Complexity, Computation Tree, Configuration, Four-Dimension, Turing machine
Abstract:	Alternating Turing machines were introduced in 1981 as a generalization of nondeterministic Turing machines and as a mechanism to model parallel computation. On the other hand, we have no enough techniques which we can show that some concrete four-dimensional language is not accepted by any space-bounded four-dimensional alternating Turing machines. The main purpose of this paper is to present a technique which we can show that some fourdimensional language is not accepted by any space-bounded four-dimensional alternating Turing machines. Concretely speaking, we show that the set of all four-dimensional input tapes over {0,l}, which each top half part is equal to each bottom half part, is not accepted by any L(m) space-bounded four-dimensional alternating Turing machines for any function L(m) smaller than log m.
PDF File:	https://alife-robotics.co.jp/members2016/icarob/data/papers/OS/OS12-4.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/

HOME