**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30753

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

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

**Abstract:**

**Keywords:**
Turing Machine,
converter,
four-dimension,
Cellular acceptor,
configuration-reader,
finite automaton,
on-line tessellation acceptor,
parallel/sequential array acceptor

**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.