k-Neighborhood Template A-Type Three-Dimensional Bounded Cellular Acceptor

Authors: Makoto Nagatomo, Yasuo Uchida, Makoto Sakamoto, Tuo Zhang, Tatsuma Kurogi, Takao Ito, Tsunehiro Yoshinaga, Satoshi Ikeda, Masahiro Yokomichi, Hiroshi Furutani

Abstract:

This paper presents a four-dimensional computational model, k-neighborhood template A-type three-dimensional bounded cellular acceptor (abbreviated as A-3BCA(k)), and discusses the hierarchical properties. An A-3BCA(k) is a four-dimensional automaton which consists of a pair of a converter and a configuration-reader. The former converts the given four-dimensional tape to the three- and two- dimensional configuration and the latter determines the acceptance or nonacceptance of given four-dimensional tape whether or not the derived two-dimensional configuration is accepted. We mainly investigate the difference of the accepting power based on the difference of the configuration-reader. It is shown that the difference of the accepting power of the configuration-reader tends to affect directly that of the A-3BCA(k) for the case when the converter is deterministic. On the other hand, results are not analogous for the nondeterministic case.

Keywords: Cellular acceptor, configuration-reader, converter, finite automaton, four-dimension, on-line tessellation acceptor, parallel/sequential array acceptor, turing machine.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124955

References:

[1] M.Blum and C.Hewitt, “Automata on a two-dimensional tape”, IEEE Symposium on Switching and Automata Theory, pp.155-160, 1967.
[2] M.Blum and W.J. Sakoda, “On the capability of finite automata in 2 and 3 dimensional spaces”, Proceedings of the 18th Annual Symposium on Foundations of Computer Sciences, pp.147-161, 1977.
[3] P.Dietz and S.R. Kosaraju, “Recognition of topological equivalence of patterns by array automata”, Journal of Computer and System Sciences, 2, PP.111-116, 1980.
[4] F.C Hennie, “One-tape off-line Turing machine computations”, Information and Control, 8(6), pp.533-578, 1965.
[5] K.Inoue and A.Nakamura, “Some notes on parallel sequential array acceptors”, The Transactions of the IECE, Japan, J58-D(3), pp.167-169, 1975.
[6] K.Inoue and A.Nakamura, “An n-dimensional on-line tessellation acceptor”, The Transactions of the IECE, Japan, J59-D(4), pp.299-236, 1976.
[7] K.Inoue, I,Takanami and H.Taniguchi, “The accepting powers of two-dimensional automata over square tapes”, The Transactions of the IECE, Japan, J63-D(2), pp.113-120, 1980.
[8] K.Inoue and I.Takanami, “A survey of two-dimensional automata theory”, Information Sciences, 55, pp.99-121, 1991.
[9] A.Ito, K.Inoue, and I.Takanami, “A note on three-way two-dimensional alternating Turning machine”, Information Sciences, 45, pp. 1-22, 1988.
[10] A.Ito, K.Inoue, I.Takanami, and Y. Wang, “The effect of inkdots for two-dimensional automata”, International Journal of Pattern Recognition and Artificial Intelligence, 9(5), pp.777-796, 1995.
[11] T.Ito, M.Sakamoto, N.Tomozoe, K.Iihoshi, H.Furutani, M.Kono, T.Tamaki, and K.Inoue, “Two-topics concerning three-dimensional synchronized alternating Turing machines”, WSEAS Transactions on Computers, 10(5), pp.2149-2155, 2006.
[12] T.Ito and M.Sakamoto, “Some accepting powers of three-dimensional synchronized alternating Turing machines”, Journal of Engineering, Computing and Architecture, Scientific Journals International, 1(1), pp.1-11, 2007.
[13] D.G. Morgenthaler, “Three-dimensional digital topology:the genus”, Technical Report, No.TR-980, Computer Science Center, University of Maryland, 1980.
[14] A.Nakamura and K.Aizawa, “On the recognition of properties of three-dimensional pictures”, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-7, pp.708-713, 1985.
[15] C.M. Park and A.Rosenfeld, “Connectivity and genus in three dimensions”, Technical Report, No.TR-156, Computer Science Center, University of Maryland, 1971.
[16] A.Rosenfeld and D.L.Milgram, “Parallel/sequential array acceptor”, Information Processing Letters, 2, pp.43-46,1976.
[17] A.Rosenfeld, “Three-dimensional digital topology”, Information and Control, 50, pp.119-127, 1981.
[18] M.Sakamoto, K.Inoue, and I.Takanami, “A two-way nondeterministic one-counter languages not accepted by any nondeterministic rebound automata”, IEICE Transactions, E73-D(6), pp.879-881, 1990.
[19] M.Sakamoto, K.Inoue, and I.Takanami, “Three-dimensionally fully space constructible functions”, IEICE Transactions on Information and Systems, E77-D(6), pp.723-725, 1994.
[20] M.Sakamoto and K.Inoue, “Three-dimensional alternating Turing machines with only universal states”, Information Sciences — Information and Computer Sciences, 95, pp.155-190, 1996.
[21] M.Sakamoto, H.Okabe, S.Nogami, S.Taniguchi, T.Makino, Y.Nakama, M.Saito, M.Kono, and K.Inoue, “A note on four-dimensional finite automata”, WSEAS Transactions on Computers, Issue 5, Vol.3, pp.1651-1656, 2004.
[22] M.Sakamoto, N.Tomozoe, H.Furutani, M.Kono, T.Ito, Y.Uchida, and H.Okabe, “A survey of automata on three-dimensional input tapes”, WSEAS Transactions on Computers, Issue 10, Vol.7, pp.1638-1647, 2008.
[23] S.Seki, “Real-time recognition of two-dimensional tapes by cellular automata”, Information Sciences, 19, pp.179-198, 1979.
[24] A.Szepietowski, “On three-way two-dimensional multicounter automata”, Information Sciences, 55, pp.35-47, 1991.
[25] H. Taniguchi, K. Inoue, I. Takanami, and S. Seki, “(k,l)-Neighborhood template A-type bounded cellular acceptors”, The Transactions of the IECE, Japan, J64-D(3), pp.244-251, 1981.
[26] H.Taniguchi, K.Fujii, K.Inoue, and I.Takanami, “k-Neighborhood template A-type two-dimensional bounded cellular acceptors (Part II)”, Technical Report, No.AL82-19, IECE, Japan, 1982.
[27] H.Taniguchi, K.Inoue, and I.Takanami, “Hierarchical properties of the k-neighborhood template A-type 2-dimensional bounded cellular acceptor”, The Transactions of the IECE, Japan, J69-D(7), pp.1025-1034, 1986.
[28] G.Tourlakis and J.Mylopoulos, “Some results on computational topology”, Journal of the Association for Computing Machinery, 20, pp.439-455, 1973.
[29] Y.Uchida, T.Ito, M.Sakamoto, T.Ide, K.Uchida, R.Katamune, H.Furutani, M.Kono, S.Ikeda, and T.Yoshinaga, “Bottom-up pyramid cellular acceptors with four-dimensional layers”, International Journal of Artificial Life and Robotics, Springer, 16(4), pp.529-532, 2012.
[30] H.Umeo, K.Morita, and K.Sugata, “Pattern recognition by automata on a two-dimensional tapes (in Japanese)”, The Transactions of the IECE, J59-P(11), pp.817-824, 1976.