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

Hierarchy Based on Configuration-Reader 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, Japan
Yasuo 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
Blum and Hewitt first proposed two-dimensional automata as computational models of two-dimensional patternprocessing－two-dimensional finite automata and marker automata, and investigated their pattern recognition
abilities in 1967. Since then, many researchers in this field have investigated the properties of automata on two- or
three-dimensional tapes. On the other hand, the question of whether or not processing four-dimensional digitalpatterns is more difficult than processing two- or three-dimensional ones is of great interest from both theoreticaland practical standpoints. Thus, the study of four-dimensional automata as the computational models offour-dimensional pattern processing has been meaningful. From this point of view, we are interested infour-dimensional computational models, In this paper, we introduce a new four-dimensional computational model,
k-neighborhood template A-type three-dimensional bounded cellular acceptor on four-dimensional input tapes, andinvestigate about hierarchy based on configuration-reader about this model.
Keywords: cellular acceptor, configuration-reader, converter, finite automaton, four-dimension, on-line tessellation
acceptor, parallel/sequential array acceptor, Turing machine

1. Introduction and Preliminaries
In 2002, we first introduced a four-dimensional
automaton, and investigated some properties [4]. In
general, 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 this paper, from thisviewpoint, we introduce a new computational model,

k-neighborhood template A-type three-dimensionalbounded cellular acceptor (abbreviated as A-3BCA(k))
on four-dimensional tapes, and discuss some basic
properties. An A-3BCA(k) consists of a pair of aconverter and a configuration-reader. The former
converts the given four-dimensional tape to thethree-dimensional configuration and the latter
determines the acceptance or nonacceptance of given
four-dimensional tape whether or not the derived

Published by Atlantis Press
Copyright: the authors
80

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

three-dimensiional configuuration is acccepted. Whenn afour-dimensioonal input tape is preesented to the
A-3BCA(k), a three-dimennsional cellular automatonn as
the converterr first reads it to the future direction at unituspeed (i.e., one three-dimeensional rectaangular array perpunit time). Frrom this proceess, the four-ddimensional taape
is converted tto a configuraation of the coonverter whichh isa state matrixx of a three-dim
mensional celllular automatton.
Second, thhree-dimensional automaaton as theconfigurationn-reader, reaads the connfiguration andadetermines its acceptaance. We say that afour-dimensioonal input tape is acccepted by the
A-3BCA(k) iff and only if the configuraation is accep
pted
by the confiiguration-readder. Thereforee, the accepting
power of thee A-3BCA(k) depends on howhto combbine
the convertter and thee configuration-reader. An
A-3DBCA(k)) (A-3NBCA(kk)) is called a k-neighborhoood
template A
A-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 callleda three-dimeensional deterministic fiinite automatton(three-dimenssional nondetterministic fiinite automatton,
deterministic three-dimeensional bouunded celluularacceptor, nonndeterministicc three-dimennsional boundded
cellular accceptor, threee-dimensionall determinisstic
on-line tesssellation acceptor,athhree-dimensio
onal
nondeterminiistic
onlineetessellatiion
accepttor,
deterministic three-way parallel/sequential arr
rray
acceptor, nonndeterministicc three-way paarallel/sequenttialarrayaccceptor,
deterministicc
four-wway
parallel/sequeential array acceptor, nondeterminisnsticparallel/sequuential
four-wayarrrayaccepttor,
three-dimensiional determ
ministic Tuuring machiine,
three-dimensiional nondeterministic Tuuring machinne).
Let T(M) be the set of fouur-dimensionaal tapes accep
pted
by a machinee M, and let L [A-3DBCA((k)] ={T|T=T((M)
for some A-3DBCA(k) M}.
M L [A-3NB
BCA(k)], etc. aredefined in thee same way ass L [A-3DBCA
A(k)].
Let Σ be a finite set of symbols. A ffour-dimensional
tape over Σ is a four-dim
mensional rectaangular arrayy ofelements of Σ. The set ofo all four-dim
mensional tap
pes
over is denotted by Σ(4). Giiven a tape x ∈ Σ(4), for eaach
integer j(1 ≤ j ≤ 4), we lett lj(x) be the length of x aloong
the jth axis. T
The set of all x ∈ Σ(4) withh l1(x) = n1, l2(x)= n2, l3(x) = n3, and l4(x) = n4 is denoteed by Σ(n1,n2,n3,n4).

W
When 1 ≤ ij ≤ lj(x) for each j((1 ≤ j ≤ 4), lett x(i1, i2, i3, i4)deenote the symbbol in x with coordinates (ii1, i2, i3, i4), ass
shhown in Fig.1. Furthermoree, we define x[(ix 1, i2, i3, i4),)
(i’’1, i’2, i’3, i’4)]], when1 ≤ ij ≤ i’j ≤ lj(x) foor each integerrj(11 ≤ j ≤ 4), as the four--dimensional input tape ysattisfying the foollowing condditions:(i)) for each j(1 ≤ j ≤ 4), lj(y) = i’j - ij + 1;(iii) 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 callc 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 off x.)
We let each sidelength of each input tape of thesee
auutomata be equivalent inn order to increase theetheeoretical interrest.

Fig. 1:Four-dimens
1
sional Input Tape.

2. Main ResulltThis sectionn investigatess how the difference ofcoonfiguration-reeader affects the acceptinng powers of
A--3BCA(k)’s. First,F
we staart to investiggate the casee
whhen the conveerter is deterministic.
Leemma 1. Let T1 = {x∈{0,1,,2}(4)| ∃n ≥ 1 [l[ 1(x) = l2(x) =l3(x)( = l4(x) = n+
+1 & ∃i(1≤i≤≤n)[x(i,n+1,n++1,n+1) = 2 &(eaach symbol on the remainingg parts iss“00”or“1”)&x[(i,,1,n+1,n+1),(ii,n,n+1,n+1)]≠≠x[(n+1,1,n+1
1,n++1), (n+1,n,n+1,n+1)]]]}. Then, (1) T1 ∈ L[N
NA-3DBCA(1)], and (2) T1 ∉ L [DA-3DB
BCA(27)].

Published by Atlantis Press
Copyright: the authors
81

Hierarchy Based on Configuration

Proof: It is easily seen that there exists a
nondeterministic three-dimensional finite automaton
accepting the set of three-dimensional tapes which are
obtained by extracting the bottom plane from the tapecontained in T1. Therefore, (1) holds. On the other hand,the proof of (2) is similar to that of Lemma 2(2) in [7].
□Lemma 2. Let T2 = {x ∈ {0,1}(4) | ∃n ≥ 1 [l1(x) = l2(x)= l3(x) = l4(x) = 2n & x[(1,1,2n,2n), (2n,n,2n,2n)] =x[(1,n+1,2n,2n), (2n,2n,2n,2n)]]}. Then, (1) T2 ∈ L[DOP-3DBCA(1)], and (2) T2 ∉ L [NO- 3DBCA(27)].
Proof: (1) Note that there exists a deterministic
one-way
parallel sequential array acceptor accepting the set oftwo-dimensional tapes obtained by extracting thebottom plane of the first cube from the tape contained in
T2. It is easily seen from this fact that (1) holds. (2) The
proof is similar to that of Lemma 2(2). Suppose that
there exists an NO-3DBCA(27) M = (R, B) accepting T2,
where R is a converter and B is a configuration-reader.
Let K be the set of each cell of B ∈ NO, and |K| = s.
For each n ≥ 1, let V (n)={ x∈{0,1}(4)| l1(x) = l2(x) = l3(x)= l4(x) = 2n & x[(1,1,1,1), (2n,2n,2n,2n-1)] ∈ {0}(4),V’(n) = V (n) ⋂ T2, W(n) = {w ∈ K(2) | l1(w) = 2n &l2(w) = 1 } (K(2) means the set of all two-dimensional
tapes over Σ .). For each x ∈ V (n), let (x) ≡ the(x) = the west
configuration of R just after reading x,
half of (x), and(x) ≡ the east half of (x).
Further, for each x ∈ V’(n), let Run(x) = {z ∈ K(2) | z isa run of B on (x) whose lower right corner symbol isan accepting state of B.} and r(x) = {z[(1,n),(2n,n)] | z ∈Run(x) } ⊆W(n). Then, the following proposition must
hold.
Proposition 1. For any two different tapes x and y inV’(n), r(x) ⋂ r(y) = ϕ.
[Proof: The proof is similar to that of Proposition 4 in
[8].
□]

be two different tapes x and y in V’(n) such that r(x) ⋂r(y) ≠ ϕ. This contradicts Proposition 1.
□
Lemma 3. Let T3 = {x∈{0,1}(4)| ∃n ≥ 1 [l1(x) = l2(x) =l3(x) = l4(x) = 2n & x[(1,1,2n,2n), (n,2n,2n,2n)] =x[(n+1,1,2n,2n),(2n,2n,2n,2n)]]}.
Then,
(1)T3
∈
L[DP-3DBCA(1)],and(2)
T3∉L[NOP-3DBCA(27)].
Proof: (1) Note that there exists a deterministic
four-way parallel sequential array acceptor accepting
the set of three-dimensional tapes which are obtained byextracting the bottom plane of the last cube from thetape contained in T3. It is easily seen, from this fact, that(1) holds.
(2) Suppose that there exists an NOP-3DBCA(27) M =(R,B) accepting T3. Let s be the number of states of eachcell of B ∈ NOP. For each n ≥ 1, let V (n) ={x∈{0,1}(4)| ∃n ≥ 1 [l1(x) = l2(x) = l3(x) = l4(x) = 2n &x[(1,1,1,1), (2n,2n,2n,2n-1)] ∈{0}(4)]}, V’(n) = V (n) ⋂T3. For each x ∈ V(n), let (x) ≡ the configuration of R
just after reading x,(x) ≡ the north half of (x), and(x) ≡ the south half of (x). Furthermore, for eachx ∈ V’(n), let conf(x) ≡ the set of possible
configuration of B just after(x) is read, when (x) is
accepted by B. (Note that (x) is accepted by B sinceeach tape in V’(n) is accepted by M.) Then, thefollowing two propositions must hold. (The proofs areomitted here. If necessary, see proofs of Lemmas 7 and
8 in [6].)Proposition 2. (i) For any two tapes x and y in V’(n)such that their [(1, 1, 2n, 2n), (n, 2n, 2n,2n)]-segments
are identical,(x) =(y), and (ii) For any two tapes
x and y in V’(n) such that their [(n + 1, 1, 2n, 2n), (2n,2n, 2n, 2n)]-segments are identical, (x) = (y).
Proposition 3. For any two different tapes x and y inV’(n), conf(x) ⋂ conf(y) = ϕ.
Proof of Lemma 3 (continued): As is easily seen,|V’(n)| = 2

Proof of Lemma 2 (continued): As is easily seen,|V’(n)| = 2
and |W(n)| ≤ s2n
Therefore, it follows for large n that |V’(n)| > |W(n)|.
Consequently, it follows for such large n that there must

Let t(n) be the total number of different configurationsof R just after reading north halves of configurations of
R just after reading tapes in V’(n). Clearly,

Published by Atlantis Press
Copyright: the authors82

M. Sakamoto, M. Nagatomo, T. Zhang, X.Feng, T. Kurogi, S. Ikeda, M. Yokomichi, H. Furutani, T. Ito, Y. Uchida and T. Yoshinaga(3) L [DO-3DBCA(k)] ⊊ L [NO-3DBCA(k)],(4) L [DB-3DBCA(k)] ⊊ L [DOP-3DBCA(k)] ⊊L [DP-3DBCA(k)], and(5) L [DO-3DBCA(k)] ⊊ L [DOP-3DBCA(k)] ⊊L [NOP-3DBCA(k)].

t(n) ≤ s2n
Therefore, it follows for large n that|V’(n)| > t(n)Consequently, it follows for such large n that there
must be two different tapes x and y in V’(n) such thatconf(x) ⋂ conf(y) ≠ ϕ. This contradicts Proposition 3.
□
Lemma 4. Let T4 be the set of three-dimensional tapes
described in Lemma 1 in [7]. Then, (1) T4∈[NB-3DBCA(1)], and (2) T4 ∉ L [DOP-3DBCA(27)].
Proof: (1) It is easily seen that there exists a
nondeterministic one-dimensional bounded cellular
automaton accepting the set of three-dimensional tapes
which are obtained by attracting the bottom plane fromthe tape contained in T4. Therefore, (1) holds. On theother hand, the proof of (2) is shown Lemma 1 in [7].
□Lemma 5. Let T5 = {x∈{0,1}(4) | ∃n ≥ 1 [l1(x) = l2(x) =l3(x) = l4(x) = 2n & [x(1,1,2n,2n), (n,n,2n,2n)]≠x[(n+1,n+1,2n,2n),(2n,2n,2n,2n)]]}. Then, (1) T5 ∈ L[NB-3DBCA(1)], and (2) T5 ∉ L [NA-3DBCA(27)].
Proof: (1) It is easily seen that there exists a
nondeterministic one-dimensional bounded cellular
automaton accepting the set of three-dimensional tapes
which are obtained by extracting the bottom plane fromthe tape contained in T5. Therefore, (1) holds. On theother hand, the proof of (2) is similar to that of Lemma
2
in
[7].
□
From the foregoing lemmas, we can obtain thefollowing theorem when the converter is deterministic.
Theorem 1. For each k ∈ {1, 7, 27},(1) L [DA-3DBCA(k)] ⊊ L [NA-3DBCA(k)] ⊊L [NB-3DBCA(k)] = L [NO-3DBCA(k)] ⊊L [NOP-3DBCA(k)] ⊊ L [NP-3DBCA(k)](2) L [DB-3DBCA(k)] ⊊ L [NB-3DBCA(k)],Proof: It is clear from Proposition 1 in [7] that theinclusion relations hold. Therefore, below, we show thatthe proper inclusion relations held for each k ∈ {1, 7,
27}.
(1): It is obvious from Proposition l in [7] that L[NB-3DBCA(k)] = L [NO-3DBCA(k)]. From Lemma1, L[DA-3DBCA(k)] ⊊ L [NB-3DBCA(k)] holds, and from
Lemma 5, L [NB-3DBCA(k)]⊊L [NB-3DBCA(k)] holds.
In addition, it is obvious from Proposition 1 in [7] that L[DOP-3DBCA(k)] ⊆ L [NP-3DBCA(k)]. It follows
from this and Lemma 2 that L [NO-3DBCA(k)] ⊊ L[NOP-3DBCA(k)] holds. Further, it is also obvious from
Proposition 1 in [7] that L [DP-3DBCA(k)] ⊆ L[NP-3DBCA(k)]. It follows from this and Lemma 3 that
L [NOP-3DBCA(k)] ⊊ L [NP-3DBCA(k)] holds.
(2) and (3) : These are easily proved from Lemma 4 andProposition 1 in [7].
(4) and (5) : These are also easily proved from Lemmas
4,5,6 and Proposition 1 in [7].
□Next, we investigate the case when the converter isnondeterministic.
Lemma 6. For each k ∈ {1, 7, 27},(1) L [NO-3NBCA(k)] ⊆ L [DA-3NBCA(k)],(2) L [NO-3NBCA(k)] ⊆ L [DB-3NBCA(k)], and(3) L [NO-3NBCA(k)] ⊆ L [DO-3NBCA(k)].
Proof: (1) We prove only L [NO-3NBCA(1)] (The othercases are proved similarly.) Let M= (R, B) be an
arbitrary NO-3NBCA(1), and let KR and KB be the set ofstates of R and B, respectively. Further, let M’ = (R’, B’)
be a DO-3NBCA(1) which acts as follows for a given
four-dimensional tape x with each sidelength is n (n ≥1).
(i) Actions of the converter R’
At each time, each (i, j, k, l)-voxel (1 ≤ i, j , k, l, ≤ n)of R’ simulates the action of the corresponding voxel of
R on x at the same time. In parallel to this action, thevoxel selects nondeterministically a state in KB (we letq(i, j, k, l) be the state) and stores the state in its state,

Published by Atlantis Press
Copyright: the authors
83

Hierarchy Based on Configuration

when the voxel reads a symbol on the top plane of thefirst cube of x. Here, q(i,j,k,l) is a guessed state of B
which the (i, j, k, l)-voxel of B will enter by reading theconfiguration of R just after reading x; q(i, j, k, l) will
have been stored in the state of the voxel until x iscompleted to read.
(ii) Actions of the configuration reader B’
For each i, j, k, l(1 ≤ i, j, k, l ≤ n), let q(i, j, k, l) be astate in KR which the (i, j, k, l)-voxel of R’ continues tosimulate the action of corresponding voxel of R andenters. B’ accepts a configuration of R’ just after readingx if and only if the following two conditions are
satisfied.
1 ⃝ For each i, j, k, l(1 ≤ i, j, k, l ≤ n), the (i, j, k, l)voxel can enter q(i, j, k, l) when it reads (i, j, k, l).
2 ⃝ q(n,n,n,n) is an accepting state of B.
It is easily seen that T(M’) = T(M) for M = (R’,B’).
This completes the proof of the lemma.
□
From Lemma 6 and from Proposition 1 in [7], we canobtain directly the following theorem when theconverter is nondeterministic.(The proof is omittied
here.) It is of great interest to compare the following
Theorem 2 with Theorem 1 mentioned for thedeterministic case.
Theorem 2. For each k ∈ {1, 7, 27}, L[DA-3NBCA(k)]= L [NA-3NBCA(k)] = L [DB-3NBCA(k)] = L[NB-3NBCA(k)] = L [DO-3NBCA(k)] = L[NO-3NBCA(k)].
3.

Conclusions

In this paper, we investigated how the difference ofthe configuration-reader affects the accepting powers of
k-neighborhood template A-type three-dimensionalbounded cellular acceptor(abbreviated as A-3BCA(k)).
As the results, we showed that when theconfiguration-reader is deterministic, the A-3BCA(k)which is the converter is nondeterministic is more
powerful than the A-3BCA(k) which is the converter isdeterministic. However, this tendency is not always true
when the configuration-reader is nondeterministic.
We conclude this paper by giving a few open
problems.

(1) Accepting powers in the case of alternating versionofconfiguration-reader.
(2) Closure properties of A-3BCA(k).
(3) Recognizability of topological four-dimensional
input tapes by A-3BCA(k).
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-line
tessellation acceptor”, The Transactions of the IECE,
Japan, J59-D(4) (1967), pp. 299-236.
3. A.Rosenfeld and D.L.Milgram, “Parallel/sequential array
acceptor”, 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-Neighborhood
template A-type two-dimensional bounded cellular
acceptor”, The Transactions of the IECE, Japan, J69-D(3)(1986), pp. 291-301.
8. H.Taniguchi, K.Inoue and I.Takanami, “Hierarchicalproperties of the k-neighborhood template A-type2-dimensional bounded cellular acceptor”, The
Transactions of the IECE, Japan, J69-D(7) (1986),
pp.1025-1034.

Published by Atlantis Press
Copyright: the authors84