OS21-1 Consideration on the Recognizability of Three-Dimensional Patterns

Title:	OS21-1 Consideration on the Recognizability of Three-Dimensional Patterns
Publication:	ICAROB2017
Volume:	22
Pages:	666-669
ISSN:	2188-7829
DOI:	10.5954/ICAROB.2017.OS21-1
Author(s):	Chongyang Sun, Makoto Sakamoto, Makoto Nagatomo, Yu-an Zhang, Shinnosuke Yano, Satoshi Ikeda, Takao Ito, Tsutomu Ito, Yasuo Uchida, Tsunehiro Yoshinaga
Publication Date:	January 19, 2017
Keywords:	connectedness, finite automaton, marker, pattern, recognizability, three-dimension, Turing machine
Abstract:	Due to the advances in computer vision, robotics, and so forth, it has become increasingly apparent that the study of three-dimensional pattern processing should be very important. Thus, the study of three-dimensional automata as the computational model of three-dimensional information processing has been signiﬁcant. During the past about thirty years, automata on a three-dimensional tape have been obtained. On the other hand, it is well-known that whether or not the pattern on a two- or three-dimensional rectangular tape is connected can be decided by a deterministic onemarker ﬁnite automata. As far as we know, however, it is unknown whether a similar result holds for recognition of the connectedness of patterns on three-dimensional arbitrarily shaped tape. In this paper, we deal with the recognizability of three-dimensional patterns, and consider the recognizability of three-dimensional connected tapes by alternating Turing machines and arbitrarily shaped tapes by k marker finite automata.
PDF File:	https://alife-robotics.co.jp/members2017/icarob/data/html/data/OS_pdf/OS21/OS21-1.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