Journal of Robotics, Networking and Artificial Life, Vol. 1, No. 1 (June 2014), 85-89

Hierarchy Based on Neighborhood Template about k-Neighborhood Template A-Type
Three-Dimensional Bounded Cellular Acceptor
Makoto Sakamoto*, Makoto Nagatomo, Tuo Zhang, Xiaoyang Feng, Tatsuma Kurogi,
Satoshi Ikeda, Masahiro Yokomichi and Hiroshi Furutani

Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan
Takao Ito
Institute of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8527, JapanYasuo Uchida
Department of Business Administration, Ube National College of Technology,Ube, Yamaguchi 755-8555, Japan
Tsunehiro Yoshinaga
Department 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
Recently, due to the advance in dynamic image processing, computer animation, augmented reality (AR), and soforth, it has become increasingly apparent that the study of four-dimensional pattern processing (three-dimensional
pattern processing with time axis) should be very important. Thus, the study of four-dimensional automata as thecomputational model of four-dimensional pattern processing has been meaningful. From this point of view, we firstintroduced a four-dimensional automaton in 2002. In the multi-dimensional pattern processing, designers often use
a strategy whereby features are extracted by projecting high-dimensional space on low-dimensional space. In thispaper, from this viewpoint, we introduce a new computational model, k-neighborhood template A-type
three-dimensional bounded cellular acceptor (abbreviated as A -3BCA(k)) on four-dimensional input tapes, anddiscuss hierarchy based on neighborhood template about A-3BCA(k).
Keywords: cellular acceptor, computational complexity, configuration-reader, converter, four-dimension, neighbor

1. Introduction and Preliminaries
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 of four
dimensional automata as the computational models offour-dimensional pattern processing has beenmeaningful. From this point of view, we first proposedfour-dimensional automata as computational models offour-dimensional pattern processing in 2002 [4], andinvestigated their several accepting powers. By the way,in the multi-dimensional pattern processing, designers
often use a strategy whereby features are extracted byprojecting high-dimensional space on low dimensional
space. So, from this viewpoint, we introduce a newcomputational model, k-neighborhood template A-type
three-dimensionalboundedcellularacceptor(abbreviated as A-3BCA(k)) on four-dimensional tapesin this paper, and discuss some basic properties. An A-3BCA(k) consists of a pair of a converter and aconfiguration-reader. The former converts the given

Published by Atlantis Press
Copyright: the authors
85

M. Sakamoto, M.
M Nagatomo, T. Zhang,
ZX.Feng, T. Kurogi, S. Ikedaa, M. Yokomichi, H.
H Furutani, T. Ito,
It Y. Uchida andd T. Yoshinaga

four-dimensioonal
tapetothhree-dimensio
onal
configurationn. The latter determinesdwhhether or not thederived threee-dimensionall configuratioon is acceptted,andconcludes the acceptance or non-accepptance of givvenfour-dimensioonal tape(see Fig.1). Whenn an input foourdimensional tape is preseented to the A -3BCA(k), a
three-dimensiional cellularr automaton asa the converrter
first reads it to the futuree direction at unit speed (ii.e.,
one three-dim
mensional recttangular arrayy per unit timme).
From this process, thee four-dimennsional tape isconverted to a configuratioon of the convverter which isi astate matrix oof a three-dim
mensional celllular automatton.
theSecond, thrree-dimensionnal automaton as
configurationn-reader readds the connfiguration andadetermines iits acceptancce. We say that an inpput
remarkable pixel or voxeel in neighbor.. In other worrds,
we deal w
with 5- andd 9-connecteedness in thetwo-dimensioonal case, andd 7- and 27-cconnectednesss inthe three-dim
mensional casee in this paperr. In Addition, in
our another paper, we mainlym
invesstigate how thedifference off configurationn-reader affeccts the accepting
powers of A -3DBC
CA(k)’s. Whhen an inpput
four-dimensioonal tape is prresented to thhe A -3BCA(k)), athree-dimensiional cellularr automaton aas the converrter
first reads it tto the future direction
dat unnit speed (i.e.,oone
three-dimensiional rectanguular array per unit time), annd a
two-dimensioonal cellular automaton aas the converrter
next reads a converted thrree-dimensionnal configuration
downward att unit speed (ii.e., one planee per unit timme).
From this process, thee four-dimennsional tape isi aconverted to a configuratioon of the convverter which isstate matrix of a two-dim
mensional celllular automatton.
Second,twthewo-dimension
nal
automaaton
asconfigurationn-reader, reaads the connfiguration andadetermines iits acceptancce. We say that an inpput
four-dimensioonal tape is accepted
aby thhe A-3BCA(k)k) if
and only iff the configuuration is acccepted by theconfigurationn-reader. Therrefore, the acccepting powerr of
the A-3BCA
A(k) depends on how too combine theAnandtheconverter
configuratioon-reader.
A-3DBCA(k)) (A-3NBCA(kk)) is called a k-neighborhoood
template AA-type threee-dimensionall determinisstic
bounded cellular acceptoor (k-neighboorhood templlate
A-type threee-dimensionall nondetermiinistic boundded
cellular accepptor). A DA[[1] (NA, DB[[5], NB, DO[[2],NO, DOP[3],, NOP, DP[3], NP, DTM[4]], NTM) is callled

fouur-dimensionaal tape is acccepted by thee A -3BCA(k)k)
if and only iff the configuuration is acccepted by theecoonfiguration-reeader. Thereffore, the acccepting powerr
off the A -3BCCA(k) depends on how to combine theecoonverter andd the conffiguration-readder. An A-3DDBCA(k) (A -3NBCA(k)) is called a k--neighborhooddtemmplate A-tyype three-ddimensional deterministicc
boounded cellullar acceptor (k-neighborhhood templatee
A--type three-ddimensional nondeterministic boundedd
cellular acceptoor). This papeer mainly invvestigates howw
thee difference of the neighhborhood tem
mplate of theecoonverter affeects the acccepting pow
wers of A-3D
DBCA(k)’s. In general, it is well known thaattwwo-dimensionaal digital pictures haave 4- andd
8-cconnectedness, and three-ddimensional digitaldpicturess
haave 6- and 26-connectedness. However, wew include theea three-dimenssional determ
ministic finitte automatonn(thhree-dimensioonal nondeterrministic finitte automatonn,deeterministic three-dimenssional bounded cellularr
acceptor, nondeeterministic three-dimensiotonal boundedd
cellular accep
ptor, three-ddimensional deterministicc
onn-line tessellation accceptor, three-dimensionaal
tessellationn
noondeterministiic
on-lineacceptorr,
deeterministic three-way parallel/sequuential arrayy
acceptor, nondeeterministic thhree-way paraallel/sequentiaal
acceeptor,
deterministic
four-wayy
arrraypaarallel/sequenttial array acceptor,
anonndeterministicc
fouur-waypaarallel/sequenntial
arrayyacceptorr,
thrree-dimension
nal determin
nistic Turinng machinee,
thrree-dimension
nal nondeterm
ministic Turiing machine)).
Leet T(M) be thee set of four-ddimensional tapestacceptedd
byy a machine M,
M and let L[[A-3DBCA(k))] = {T|=T(M)M)
forr some A-3D
DBCA(k) M}.. L[A-3NBCAA(k)], etc. aree
deefined in the saame way as L[A-3DBCA(kLk)].

Fig. 1:Four-dimens
1sional Input Tape.
Let Σ be a fiinite set of syymbols. A fouur-dimensional
tappe over Σ is a four-dimennsional rectanggular array ofeleements of Σ. The set of all four-dimeensional tapess

Published by Atlantis Press
Copyright: the authors
86

Hierarchy Based on Neighborhood

over Σ is denoted by Σ(4). Given a tape x∈Σ(4), for each
integer j(1≤ j ≤4), we let lj(x) be the length of x along
the jth axis. The set of all x∈Σ(4) with l1(x) = n1, l2(x) =n2, l3(x) = n3, and l4(x) = n4 is denoted by Σ(n1,n2,n3,n4).
x[(i1, i2, i3, i4), (i’1, i’2, i’3, i’4)], when 1 ≤ ij ≤ i’j≤ lj(x) for
each integer j(1 ≤ j ≤ 4), as the four-dimensional input
tape y satisfying the follwing conditions:(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 call x[(i1, i2, i3,i4), (i’1, i’2, i’3, i’4)] the [(i1, i2, i3, i4), (i’1, i’2, i’3,i’4)]-segment of x.)
We let each sidelength of each input tape of these
automata be equivalent in order to increase thetheoreticalinterest.
2.

When 1 ≤ ij ≤ lj(x) for each j(1 ≤ j ≤ 4), let x(i1, i2, i3, i4)denote the symbol in x with coordinates (i1, i2, i3, i4).
Furthermore, we define
Also, for each x ∈ V (n) and for each i(1≤ i≤ n), let(x) ≡ the configuration of R just after reading x,(x)≡ [(1,1,n+1,i),(n+1,n+1,n+1,i)]-segment of (x), and(x) ≡ the [(1,1,n+1,i),(n+1,n+1,n+1,i)]-segment of(x). Further, for each n ≥ 1, let C(n) = { (x) | x∈W(n)}.
Then, the following two propositions must hold.
Proposition 1. For each i(1 ≤ i ≤ n),(i) For any two tapes x, y ∈ V (n) such that their[(1,1,1,i),(n+1,n+1,n,i)]-segment are identical,(x) =(y),(ii) For any two tapes x, y ∈ V (n) such that their[(1,1,1,i),(n+1,n+1,n,i)]-segments are identical,(x) =(y).

Main Result

This section investigates how the difference of theneighborhood template of converter affects theaccepting powers of A-3BCA(k)'s. First, we investigate
the difference between the accepting powers of
one-neighbor and seven-neighbor.

[proof: Since R is deterministic and is of one-neighbor,the proof is easy to see.
□]Lemma 1. Let T1 = {x∈{0,1,2}(4)| ∃n ≥ 1 [l1(x) = l2(x) =l3(x) = l4(x) = n & ∀i(1≤i≤n)[x[(1,1,n,i), (n,n,n,i)] =x[(1,1,n,i),(n,n,i,n)]]]}.
Then,(1)T1 ∈ L[DA-3DBCA(7)]⋂ L[DB-3DBCA(7)] ⋂L[DO-3DBCA(7)], and (2) T1 ∉ L [TM-3NBCA(1)].

[Proof: Suppose, on the contrary, that(x) =(y).
Consider the tapes z ∈ V (n) satisfying the following
two conditions for each i(1 ≤ i ≤ n):1⃝z[(1,1,1,i),(n+1,n+1,n,i)]=x[(1,1,1,i),(n+1,n+1,n,i)],2 ⃝ z[(1,1,n+1,i), (n+1,n+1,n+1,i)] = y[(1,1,n+1,i),(n +1,n + 1,n + 1,i)].
Clearly, x ∈ W(n) ⊆ T1. Thus x is accepted by M.
Therefore, (x) is accepted by B.
On the other hand, it follows from 1 ⃝ and Proposition
1 (i) that(x) =(y), and it follows from 2 ⃝ andProposition 1 (ii) that(x) =(y). Further, from theforegoing assumption(z) =(y), it follows that(z) =(x). From(z) =(x) and(z) =(x),it follows that (z) = (x).
Since (x) is accepted by B, (z) is also accepted by
B. Consequently, z is also accepted by M. This is acontradiction.(Note that z ∉ T1.)□]Proof: (1) The proof is omitted here since it is easy toprove. (If necessary, see the proof of Lemma 1(1) in[6].) (2) We can show T1 ∉ L[TM-3NBCA(1)] by using
the same technique as in the proof of theorem 1 in [7].
Suppose that there exists a TM-3NBCA(1) M = (R,B)
accepting T1, where R is a converter and B is aconfiguration-reader.
Let S be the number of states of each cell of R. For eachn ≤ 1, let
V (n)={x∈{0,1}(4)|l1(x) = l2(x) = l3(x) = l4(x) = n + 1 &∀i(1≤i≤n)x[(1,1,1,i),(n+1,n+1,n,i)∈{0}(3),(3)x[(1,1,n+1,n+1), (n+1,n+1, n+1, n+1)] ∈ {0} } andW(n) = V (n) ⋂ T1.

Proposition 2. For any two different tapes x, y ∈ W(n),(x) ≠(y).

Proof of Lemma 1(continued) : As is early seen,|W(n)| = 2n(n+1)(n+1) and |C(n)| ≤ s(n+1)(n+1)

Published by Atlantis Press
Copyright: the authors
87

M. Sakamoto, M. Nagatomo, T. Zhang, X.Feng, T. Kurogi, S. Ikeda, M. Yokomichi, H. Furutani, T. Ito, Y. Uchida and T. Yoshinaga

Therefore, it follows for large n that |W(n)| < |C(n)|.
Consequently, it follows for such large n that there mustbe two different tapes x,y∈W(n) such that(x) ≠(y).
Thiscontradicts
Proposition
2.
□Theorem 1. For each A ∈ {DA, NA, DB, NB, DO,NO, DOP,NOP, DP, NP, TM} and for each X ∈{D, N},
L [A-3XBCA(1)] ⊊ L [A-3XBCA(7)].
Proof: The inclusion relation holds immediatelydefinitions. Further, it is easily seen from Lemma 1 andProposition 1 in [1] that the theorem holds.
□We investigate the difference between the acceptingpowers
ofseven-neighborhood
andtwenty-seven-neighbor. As shown later in Theorem 2and 3, different situations emerge depending on whether
the converter is deterministic or nondeterministic. First,we consider the case when the converter isdeterministic.
Theorem 2. For each A ∈ { DA, NA, DB, NB, DO,NO }, L [A-3DBCA(7)] ⊊ L [A-3DBCA(27)].
Proof : The inclusion relation holds immediately fromdefinitions. Further, it is easily seen from Theorem 3and Proposition 1 in [7] that the theorem holds.
□We conclude this section by investigating thedifference between the accepting powers ofseven-neighbor and twenty-seven-neighbor for the casewhen converter is nondeterministic.
Theorem 3. For each A ∈ { DA, NA, DB, NB, DO,NO, DOP, NOP, DP, NP, TM }, L [A-3DBCA(7)] = L[A-3NBCA(27)].
Proof: For each A ∈ { DA, NA, DB, NB, DO, NO,DOP, NOP, DP, NP, TM }, it is obvious that
L[A-3NBCA(7)] ⊆ L[A-3NBCA(27)] from definitions.
Below, we show that L [A-3NBCA(7)] ⊇L[A-3NBCA(27)]. Given an A ∈ { DA, NA, DB, NB,DO, NO, DOP, NOP, DP, NP, TM }, we let M = (R, B)
be an A-3NBCA(27). We now consider the
A-3NBCA(7) M’ = (R’, B’) which acts as follows.

Suppose that a four-dimensional input tape x with eachsidelength n (n ≥ 2) is presented to M. Since R’ hasseven neighbors, each voxel of R’ can refer directly tothe states of , remarkable, north, south, east, west, up,
and down neighbor voxels, but not other neighborvoxels. Therefore, by guessing the seven states ofneighbor voxels which cannot be referred to directly,
and by checking whether or not this guess is convect,
each voxel of R’ simulates the action of thecorresponding voxel of R. In fact, M’= (R’, B’) acts asfollows.
(i) Action of the converter R’
R’ starts to act with the same initial configuration with
one of R. That is, every voxel reading the boundary
symbol is in q#, which is the boundary state of R, and allof the other voxels are in q0, which is the initial state of
R. Next, the seven states of neighbor voxels of R is
easily simulated by R’, and the twenty states of otherneighbor voxels of R are guessed nondeterministicallyby R.
(ii) Action of the configuration-reader B’
B’ accepts the configuration of R’ just after readingx (say, (x)), if and only if the following 1 ⃝ , 2 ⃝ , 3 ⃝ aresatisfied.
1 ⃝ For each i, j, k (1 ≤ i, j, k ≤ n), no (i, j, k)-voxel enters
the dead state.
2 ⃝ The information guessed by any (i, j, k)-voxel on thelast
three-dimensional
rectangulararrayoffour-dimensional input tape is correct.
3 ⃝ Let h be a mapping extracting one state, which isobtained by simulating the action of the corresponding
voxel of R, from the states stored in the state of (i, j,k)-voxel. Let h be a projection which is obtained byextending the mapping h. Then h( (x)) is accepted by B.
In 1 ⃝ and 2 ⃝ in the foregoing, check whether or not
R’ can correctly simulate the action of R. Therefore, it isclear thet h( (x)) reflects the configuration of R justafter reading x, if 1 ⃝ and 2 ⃝ are satisfying. It is easily
seen that T(M’) = T(M) for M = (R’, B’). Thus, L[A-3NBCA(7)]⊇L [A-3NBCA(27)]. This completes theproof of the theorem.
□

Published by Atlantis Press
Copyright: the authors
88

Hierarchy Based on Neighborhood

3.

Conclusions

In this paper, we investigated how the difference ofneighborhood template of the converter affects theaccepting powers of k-neighborhood template A-type
three-dimensionalboundedcellular
acceptor(abbreviated as A-3BCA(k)). Generally speaking, when
the converter is deterministic, the accepting power ofthe A-3BCA(k) tends to be more powerful as the numberof neighborhood cells of the converter increases or theaccepting power of the configuration-reader is more
powerful. However, this tendency is not always true
when the converter is nondeterministic.
We conclude this paper by giving two open problems.
(1) For each A ∈{DOP, NOP, DP, NP, DTM, NTM}, L[A-3DBCA(7)] ⊊ L [A-3DBCA(27)]?
(2) L [NO-3NBCA(7)] ⊊ L [DOP-3NBCA(27)]?
References
1. M.Blum and C.Hewitt, “Automata on a two-dimensionaltape”, IEEE Symposium on Switching and Automata
Theory (1967), pp. 155-160.
2. K.Inoue and A.Nakamura,“An n-dimensional on-linetessellation acceptor”, The Transactions of the IECE,Japan, J59-D(4) (1967), pp. 299-236.
3. A.Rosenfeld and D.L.Milgram, “Parallel/sequential arrayacceptor”, Information Processing Letters, 2 (1976), pp.
43-46.
4. M.Sakamoto,
H.Okabe,S.Nagami,
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 (2004), pp.
1651-1656.
5. S.Seki, “Real-time recognition of two-dimensional tapesby cellular automata”, Information Sciences, 19 (1976),
pp. 179-198.
6. H.Taniguchi, K.Fujii, K.Inoue and I.Takanami,“k-Neighborhood template A-type two-dimensionalbounded cellular acceptors (Part II)”, Technical Report
No. AL82-19, IECE, Japan (1982).
7. H.Taniguchi, K,Inoue and I.Takanami, “k-Neighborhoodtemplate A-type two-dimensional bounded cellularacceptor”, The Transactions of the IECE, Japan, J69-D(3)(1986), pp. 291-301.

Published by Atlantis Press
Copyright: the authors89