Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 4 (March 2016), 268-271

Some properties ofk-neighborhood Template A-type two-dimensional bounded cellular acceptors
Makoto Nagatomo*, Makoto Sakamoto, Hikaru Susaki, Tuo Zhang,Satoshi Ikeda and Hiroshi Furutani

Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan
Tsutomu Ito, Takao Ito
Institute of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8527, Japan
Yasuo Uchida
Department of Business Administration, Ube National College of Technology,Ube, Yamaguchi 755-8555, Japan
Tsunehiro YoshinagaDepartment of Computer Science and Electronic Engineering, Tokuyama college of Technology, Shunan, Yamaguchi 745-8585, Japan*

Corresponding author, E-mail: sakamoto@cs.miyazaki-u.ac.jp
Tel: +81-985-58-7392, Fax: +81-985-58-7392

Abstract
In this paper, we investigate multi-dimensional computational model, k-neighborhood template A-type
three-dimensional bounded cellular acceptor on four-dimensional tapes, and discuss some basic properties. Thismodel consists of a pair of a converter and a configuration-reader. The former converts the given four-dimensional
tape to three-dimensional configuration. The latter determines whether or not the derived three-dimensional
configuration is accepted, and concludes the acceptance or non-acceptance of given four-dimensional tape. We
mainly investigate some open problems about k-neighborhood template A-type three-dimensional bounded cellular
acceptor on four-dimensional tapes whose configuration-readers are L(m) space-bounded deterministic(nondeterministic) three-dimensional Turing machines.
Keywords: configuration-reader, converter, four-dimension, neighbor, space-bounded, Turing machine

1. Introduction
Due to the advances in many application areas suchas computer animation, dynamic image processing, andso on, the study of four-dimensional pattern processing
has been of crucial importance. Thus, the study offour-dimensional automata as the computational models
of four-dimensional pattern processing has beenmeaningful. From this point of view, we first proposedfour-dimensional automata as computational models offour-dimensional pattern processing in 2002, andinvestigated their several accepting powers[2]. By theway, in the multi-dimensional pattern processing,designers often use a strategy whereby features are
extracted by projecting high-dimensional space on
low-dimensional space. So, from this viewpoint, we
introduce a new computational model, k-neighborhood
template A-type three-dimensional bounded cellularacceptor(abbreviatedas
A-3BCA(k))
onfour-dimensional tapes, and discuss some basic
properties[3]. An A-3BCA(k) consists of a pair of aconverter and a configuration-reader. The former
converts the given four-dimensional tape tothree-dimensional configuration. The latter determines

Published by Atlantis Press
Copyright: the authors
268Makoto Nagatomo, Makoto Sakamoto, Hikaru Susaki, Tuo Zhang, Satoshi Ikeda, Hiroshi Furutani, Tsutomu Ito, Takao Ito, Yasuo Uchida, Tsunehiro
Yoshinaga

whether or not the derived three-dimensional
configuration is accepted, and concludes the acceptanceor non-acceptance of given four-dimensional tape.
When an input four-dimensional tape is presented to theA-3BCA(k), a three-dimensional cellular automaton as
the converter first reads it to the future direction at unit
speed (i.e., one three-dimensional rectangular array perunit time). From this process, the four-dimensional tapeis converted to a configuration of the converter which isa state matrix of a three-dimensional cellular automaton.
Second,three-dimensional
automatonastheconfiguration-reader reads the configuration anddetermines its acceptance. We say that an input
four-dimensional tape is accepted by the A-3BCA(k) ifand only if the configuration is accepted by theconfiguration-reader. Therefore, the accepting power ofthe A-3BCA(k) depends on how to combine theconverter and the configuration-reader. An A-3DBCA(k)(A-3NBCA(k)) is called a k-neighborhood templateA-type three-dimensional deterministic bounded cellular
acceptor(k-neighborhoodtemplateA-typethree-dimensional nondeterministic bounded cellularacceptor). This paper mainly investigates some open
problems about accepting powers of A-3DBCA(k)’swhose configuration-readers are L(m) space-bounded
deterministic (nondeterministic) three-dimensional
Turing machines[1].
2. Preliminaries
Definition 2.1. Let Σ be a finite set of symbols. A
three-dimensional tape over Σ is a four-dimensional
rectangular array of elements of Σ . The set of all
four-dimensional tapes over Σ is denoted by Σ （４）.
Given a tape x∈ Σ （４）, for each integer j( 1 ≤ j ≤ 4 ), wem j (x)letbe the length of x along the j-th axis. Thex
set of all ∈ Σ with l1(x)=m1, l2(x)=m2, l3(x)=m3, andl4(x)=m4 denoted by ∑ (m1,m2,m3,m4). If 1 ≤ij ≤lj(x) foreach j (1 ≤ j ≤ 4) , let x(i1,i2,i3,i4) denote the symbol inx with coordinates (i1,i2,i3,i4). Furthermore, we define1 ≤ i j ≤ i ' j ≤ l j ( x)x[(i1,i2,i3,i4),(i1’,i2’,i3’,i4’)], whenforj(1≤j≤4)
each integer, as the four-dimensional tape ysatisfying the following (i) and (ii):(i)
for each j(1≤j≤4), lj(y)=i’j-ij+1;(ii)
for each r1, r2, r3, r4(1≤r1≤l1(y), 1≤r2≤l2(y),1≤r3 ≤l3(y), 1≤r4 ≤l4(y)), y(r1, r2, r3, r4) =x(r1+i1-1, r2+i2-1, r3+i3-1, r4+i4-1). (We callx[(i1, i2, i3, i4), (i’1, i’2, i’3, i’4)] x[(i1, i2, i3, i4),(i’1, i’2, i’3, i’4)]-segment of x.);We now introduce a k-neighborhood template A-type
three-dimensionalboundedcellularacceptor(A-3BCA(k)), which is a main object of discussion inthis paper.
Definition 2.2. Let A be the class of an automaton
moving on a three-dimensional configuration. Then, an
A-3BCA(k) M is defined by the 2-tuple M=(R,B). R andB are said to be a converter and a configuration-reader
in view of its property, respectively.
(1) R is a three-dimensional infinite array consists ofthe same finite state machines and is defined by the6-tulpe
M = (Z2, N2, K, Σ, σ, q0), where① Z is the set of all integer, and the finite statemachines are assigned to each point of
Z3(=ZxZxZ). The finite state machine situatedat coordinates (i,j,k) ∈ Z3 is called the(i,j,k)-th cell and denoted by A(i,j,k),② N3( ⊆ Z3) represents the neighborhood
template of each cell and N3 = {(i,j,k) |－1≤i,j,k≤1},③ K is a finite set of states of each cell andcontains q#(the boundary state) and q0 (theinitial state),④ Σ is a finite set of input symbols (# ∉ Σ isthe boundary symbol),⑤ σ:K27 x (Σ∪{#}) →2K is the cell statetransition function. Let q1.j,k(t) be the state of
the A(i,j,k) at time t. Thenqi,j,k(t+1) ∈ σ (qi-1,j-1,k-1(t), qi-1,j,k-1(t), qi-1,j+1,k-1(t),qi,j-1,k-1(t), qi,j,k-1(t), qi,j+1,k-1(t), qi+1,j-1,k-1(t), qi+1,j,k-1(t),qi+1,j+1,k-1(t), qi-1,j-1,k(t), qi-1,j,k(t), qi-1,j+1,k(t), qi,j-1,k(t),qi,j,k(t), qi,j+1,k(t), qi+1,j-1,k(t), qi+1,j,k(t), qi+1,j+1,k(t),qi-1,j-1,k+1(t), qi-1,j,k+1(t), qi-1,j+1,k+1(t), qi,j-1,k+1(t), qi,j,k+1(t),qi,j+1,k+1(t), qi+1,j-1,k+1(t), qi+1,j,k+1(t), qi+1,j+1,k+1(t), a),wher a is the symbol on the A(i,j,k) at time t. If qi,j,k(t) =q#, however, qi,j,k(t+1) = {q#} for each (i,j,k) ∈ Z3 andeach t ≥ 0.
(2) A set of input symbols of B is K－{q#} (where B∈ A). Intuitively, M=(R,B) moves as follows, given
a four-dimensional input tape x ∈ Σ (m1,m2,m3,m4)(m1, m2,m3,m4 ≥ 1) (x is surrounded by theboundary symbol #). First, each cell A(i,j,k) ofR(1≤i≤m1, 1≤j≤m2, 1≤k≤m3) reads each symbolon the first three-dimensional rectangular arrayx(i,j,k,1) in the initial state q0, and all of the othercells read the boundary symbols #’s in theboundary state q#’s at time t=0. Starting from thisPublished by Atlantis Press
Copyright: the authors269

Some properties of k-neighborhood

condition, R keeps reading x according to the cellstate transition function, and moving down the cellarray by one three-dimensional rectangular array,every time R reads one three-dimensional
rectangular array all. Next, B starts to moveregarding a three-dimensional configuration of R
just after R finished reading x as athree-dimensional input tape and determines
whether or not can accept the configuration. If B
accepts it, x is said to be accepted by M. Let T(M)be the set of all accepted three-dimensional tape byM.
Definition 2.3. An A-3BCA in Dfinition 2.2 is called a27-neighborhood template A-3BCA. If we deal with
east, west, south, north, up, down neighboring cells andremarkable cell, we call it 7-neighborhood template
A-3BCA. If we deal with only remarkable cell, we call it
1-neighborhood template A-3BCA. From now on, wedenote k-neighborhood template A-3BCA by A-3BCA(k)(k ∈ {1,7,27}) .
Definition 2.4. If the image generated by σ inDefinitions 2.2 and 2.3 is a singleton, the converter issaid to be deterministic, and if not, it is said to benondeterministic. An A-3BCA(k) (k ∈ {1,7,27}), whichconverter is deterministic (nondeterministic), is said tobe a deterministic (nondeterministic). A-3BCA(k) anddenoted by A-3DBCA(k) (A-3NBCA(k)).
We now consider the class of three-dimensional
automata described by the following abbreviations as
the class of the configuration-reader of A-3BCA(k) A. In
this paper, we assume that the reader is familiar with thedefinition of these automata. If necessary, see[2].
3-DTM(L(m)) … The class of L(m) space-bounded
deterministic three-dimensional Turing machine
3-NTM(L(m)) … The class of L(m) space-bounded
nondeterministic three-dimensional Turing machine
DO… The class of deterministic
three-dimensional on-line tessellation acceptor
DB …
The class ofdeterministic two-dimensional bounded cellular
acceptor
For example 3-DTM(L(m))-3DBCA(27) represents
such the class as its converter is deterministic and27-neighborhood, and its configuration-reader is anL(m) space-bounded deterministic three-dimensional
Turing machine. Moreover, for any A ∈ {3-DTM(L(m)),

3-NTM(L(m))}, for any X ∈ {D, N} and for any k ∈ {1,7,27}, the class of set of all four-dimensional tapes
accepted by A-3XBCA(k) is denoted by L[A-3XBCA(k)].
We let each side-length of each input tape of these
automata be equivalent in order to increase thetheoretical interest.
3.

Main results

In this section, we discuss some properties of
A-3BCA(k)’s whose configuration-readers are L(m)space-bounded
deterministic(nondeterministic)
three-dimensional Turing machines.
First, we show that a relationship between determinism
and nondeterminism, when we use L(m) space-bounded
three-dimensional Turing machines for any L(m) > m3
as the configuration-readers.
Theorem
3.1.
ForanyX ∈ {D,N},
L[3-XTM(m3)-3DBCA(1)]=L[3-XTM(m3)-3NBCA(1)].
Proof: From above definition, it is obvious that
L[3-XTM(m3)-3DBCA(1)]⊆L[3-XTM(m3)-3DBCA(1)]. We below show that
L[3-XTMs(m3)-3NBCA(1)]⊆L[3-DTM(m3)-3DBCA(1)] (we can prove another case(i. e. , X=N) in the same way).
Now, let M=(R,B) ((R=Z2, N2, K, Σ, σ, q0), B=(K,Q, Σ, Γ , δ , p0, F)) be some 3-DTM(m3)-3NBCA(1).
Then, we consider an M’=(R’,B’) (R’=(Z3, N3, K’, Σ,σ’, q0), B’=(K’, Q, Σ, Γ , δ ’, p0’, F’)) constructed asfollows.
(1) Construction of R’① K’=2(K-{q#}) ⋃ {q#}, q0’={q0}.
② For any a ∈ Σ and any K’’ ∈ K’-{q#},σ’(K’’, a) =  σ(p, a).
q∈K ''(2) Construction of B’
For any p ∈ Q and any K’’ ∈ K’-{q#},δ ’(p, K’’) = r∈K '' δ (p, r).
Intuitively, we explain the movement of M’=(R’, B’)constructed in this way. Let us suppose that afour-dimensional tape x ∈ Σ(4)+ is given to M’. R’ is
one-neighborhood, so we can consider each cell of R’ asusual one-dimensional finite automata. Then, each cellof R’ moves to store all states that each corresponding
cell of R can enter in each state at each time by using
the well-known subset construction method (see (1)).
B’ nondeterministically chooses only one state fromeach state of each cell of R’, and simulates thePublished by Atlantis Press
Copyright: the authors
270

Makoto Nagatomo, Makoto Sakamoto, Hikaru Susaki, Tuo Zhang, Satoshi Ikeda, Hiroshi Furutani, Tsutomu Ito, Takao Ito, Yasuo Uchida, Tsunehiro
Yoshinaga

movement of B regarding the selected states as the input
symbol. If B’ can not accept the input, B’ selects thenext input and simulates the movement of B. From theway such as the above manner, B’ checks the all input
patterns, and if B’ can accept one input, B’ can accept
the configuration of R’ (see (2)).
It is clear that T(M’)=T(M) for M’=(R’,B’) constructedinthismanner.
□Next, we show that there exists a language accepted by
a 3-DTM(0)-3NBCA(1), but not accepted by any
3-NTM(L(m))-3DBCA(27) for any L(m)) = o(ℓog m).
Theorem 3.2. For any function L(m)= o( ℓ og m),
L[3-DTM(0)-3NBCA(1)]-L[3-NTM(L(m))-3DBCA(27)] ≠ φ.
Proof: Let C={w02w12…2wk | k ≥ 1 & ∀ i(0≤i≤k)[w1 ∈ {0,1}+] & ∃ j(0≤j≤k ) [w0=wj r]}(where, for any
one-dimensional tape w, wr denotes the reversal of w),
and T1={x ∈ {0,1,2} (4)+ | ∃ m>3[ℓ1(x)=ℓ2(x)=ℓ3(x)=ℓ4(x)=m & x[(1,1,m,m), (1,m,m,m)] ∈ C]}. Then, by using atechnique similar to that in the proof of Lemma 2(1)in [4], we can show that T1 is accepted by
3-DTM(0)-3NBCA(1), but not accepted by any
3-NTM(L(m))-3DBCA(27) for any L(m))= o(ℓog m).
□

4. Conclusion
We conclude this paper by giving the following
problem. For any X ∈ {D,N} and any L(m) (log m≤
L(m) and L(m) = o(m2)), L[XTM(L(m)) – 3DBCA(1)] ⊊L [XTM(L(m)) –3NBCA(1)] ?
References
1. M. Sakamoto, H. Okabe, and K. Inoue, “Some propertiesoffour-dimensional
finiteautomata”,
2002
Chugoku-Section Joint Convention Record of Institutesof Electrical and Information Engineering, Shimane,Japan (2002), p.351.
2. M. Sakamoto, “Three-dimensional alternating Turingmachines”, Ph.D. Thesis, Yamaguchi University (1999).
3. M. Sakamoto, M. Nagatomo, X. Feng, T. Kurogi, T.
Zhang, T. Ito, Y. Uchida, T. Yoshinaga, S. Ikeda, M.
Yokomichi, and H. Furutani, “Hierarchy based onk-neighborhood template about k-neighborhood templateA-type three-dimensional bounded cellular acceptor”,
Proceedings of the International Conference on Artificial
Life and Robotics (ICAROB2014), Compal Hall, Oita,Japan, OS9-1 (2014)
4. H. Taniguchi, K. Inoue, and I. Takanami,“k-neighborhood template A-type 2-dimensionalbounded cellular acceptor”, IECE of Japan Transactions(D), Vol.69, No.3 (1986), pp.291-301.

Corollary 3.1. For any L(m) = o(log m) and any X ∈{D,N},
L[3-XTM(L(m))-3DBCA(1)]⊊L[3-XTM(L(m))-3NBCA(1)].
Remark 3.1. By using a technique to that in the proofof Theorem 3 in [4], we can show that for any function
L(m) and any k ∈ {7,27}, L[3-XTM(L(m))-3DBCA(k)]⊊L[3-XTM(L(m))-3NBCA(k)].

Finally, by using the well-known technique, we canshow that there exists a language accepted by a
DO-3NBCA(1) and a DB-3NBCA(1), but not acceptedby any 3-DTM(L(m)) – 3DBCA(27) for any function L(m) = o(log m).
Theorem 3.3. For any function L(m) = o(logm), (L[DO-3NBCA(1)]⋂L[DB-3NBCA(1)])L[3-DTM(L(m))-3DBCA(27)] ≠ φ.

Published by Atlantis Press
Copyright: the authors
271