Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://acat02.sinp.msu.ru/presentations/severyanov/Severyanov-poster.ps Äàòà èçìåíåíèÿ: Thu Jul 18 11:46:25 2002 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 20:35:07 2012 Êîäèðîâêà:

An Evolving Algebra Approach to Formal Description of
one class of Automata Networks
V. M. Severyanov 1
Laboratory of Information Technologies
Joint Institute for Nuclear Research
141980 Dubna, Moscow region, Russia
Abstract
The Automata Networks considered here and called Hyperbolic Cellu­
lar Automata are based on Iterated Function Systems and originally were
designed for constructing fractal objects. However, they are in their own
right and can be studied, for example, in the context of the computer
simulation theory. Hyperbolic Cellular Automata can be considered as a
generalization of Cellular Automata: the main di#erence lies in the fact
that a hyperbolic cellular automaton has non­regular structure of the cell
neighborhood system. Evolving Algebras (known also as Abstract State
Machines) have been proposed by Yuri Gurevich as models for arbitrary
computational processes. They are finite many­sorted dynamic algebras
representing state transitions and describing operational semantics of dis­
crete dynamical systems. They may be tailored to any desired level of
abstraction. System states are represented here as static algebras, the dy­
namics is described by a set of transition rules. Evolving Algebras provide
a formal method for executable specifications. In the talk an evolving al­
gebra approach to formal description of Hyperbolic Cellular Automata is
presented.
1 Introduction
Automata Networks were originally introduced in [1, 2, 3, 4] as models for physical
and biological phenomena. Automata networks are discrete dynamical systems [5].
The state space of an automata network is defined by a graph, where each vertex
takes state in a finite set and arcs represent vertex dependencies. The state of a
vertex is changed according to a transition rule which takes into account only the
state of its neighbors. The global dynamics is determined by a strategy of the local
transition rules application.
Two important classes of Automata Networks are Cellular Automata and Neural
Networks.
1 severyan@jinr.ru
1

Hyperbolic Cellular Automata (HCA) are Automata Networks based on Iterated
Function Systems [6] and originally were designed for constructing fractal objects
[7, 8]. However, they are in their own right and can be studied, for example, in
the context of the computer simulation theory [9]. Hyperbolic Cellular Automata
can be considered as a generalization of Cellular Automata: the main di#erence
lies in the fact that a hyperbolic cellular automaton has non­regular structure of
the cell neighborhood system. The distinguishing feature of a Hyperbolic Cellular
Automata is that its neighborhood system is determined by a Hyperbolic Iterated
Function System.
A Hyperbolic Iterated Function System (IFS) specifies a discrete dissipative dy­
namical system. An IFS consists of a set of contractive functions on a complete
metric space which induces a more complex contractive function F acting on the
set of compact subsets of the metric space. Due to the contractivity of F there is
a unique attractor A F that satisfies A F = F (A F ). Furthermore, any set A will be
eventually mapped onto the attractor A F under repeated application of the function
F . Usually contractive a#ne transformations are used for the specification of an IFS.
Evolving Algebras (known also as Abstract State Machines) have been proposed by
Yuri Gurevich [10, 11] as models for arbitrary computational processes. They are
finite many­sorted dynamic algebras representing state transitions and describing
operational semantics of discrete dynamical systems. They may be tailored to any
desired level of abstraction. System states are represented here as static algebras,
the dynamics is described by a set of transition rules. Evolving Algebras provide a
formal method for executable specifications.
Several approaches are possible to using Evolving Algebras for specification of Hy­
perbolic Cellular Automata. One of them is outlined in the present talk as the
first step on the way of applying Evolving Algebra formalism to Hyperbolic Cellular
Automata.
2 Iterated Function Systems
Aa Iterated Function System is a structure
F = ((X, d), f 1 , f 2 , ..., f N ), (1)
where (X, d) is a complete metric space, with metric d, f i : X # X, a contiguous
function #i. An IFS F induces an operator F : H(X) # H(X), where H(X), the
space of all compact subsets of X
F =
q
#
i=1
f i . (2)
The metric space (H(X), h), with Hausdor# metric h, is also complete. When the
2

functions f i are contractions, the IFS is hyperbolic. In this case, there is a compact
subset A F of X which is the fixed point of the operator F
#A F # H(X) : A F = F (A F ). (3)
Such a set is called the attractor of the IFS F . The pair (H(X), F ) is a set dynamical
system whose attractive point is a set (rather than a point) ­ the attractor A F .
Realizing the dynamics of such a dynamical system, we can build a fractal set.
The Hausdor# metric is defined as follows:
h(A, B) = max(d s (A, B), d s (B, A)), A, B # H(X), (4)
where
d s (A, B) = max
x#A
min
y#B
(d(x, y)).
We are dealing here with hyperbolic IFSs with all f i a#ne transformations.
2.1 Fractal Approximation of Sets
We can conveniently work in the unit square S = [0, 1] â [0, 1] # IR 2 S = [0, 1] â
[0, 1] # IR 2 for the space X. The IFS under consideration is appropriately scaled to
fit into S.
In practice, we are dealing with approximations of fractals rather than with fractals
themselves. We work not in the space X but in its pixel representation ”
X and,
therefore, we deal not with (H(X), h) but with (H( ”
X), h) and, correspondingly,
with ”
F = ( ”
f 1 , . . . , ”
f q ) and ”
S. In what follows under S, F and f we mean ”
S, ”
F and
”
f , respectively.
One way to build a fractal, specified by IFS, looks as follows. We take an initial
A 0 # H(X) and define
A n+1 = F (A n ) #
q
#
i=1
f i (A n ), n = 0, . . . , #. (5)
The sequence {A n } # n=0 converges to A F in the Hausdor# metric. We do N itera­
tions of F . When the number N of iterations becomes great enough, we have an
approximation
F N (A 0 ) # A F . (6)
3 Hyperbolic Cellular Automata
We define a Hyperbolic Cellular Automaton (HCA) # as a structure
(C, A, S 0 , N, #), (7)
where
3

. C is a set of cells;
. A is an alphabet of states (attributes);
. S : C # A is a state, S 0 an initial state;
. N : C # P(C) is a neighborhood system; P(C) is the power­set of C,
#c # C : N(c) is the neighborhood of c;
. # : # # # is a global dynamic rule (GDR), # = {S | S is a state}.
# n : S n-1 #-# S n n = 1, 2, . . . , M (8)
The global dynamic rule # comes about from the local dynamic rules (LDRs)
# c : #N(c) # A, (9)
where SN(c) is the restriction of S to N(c). Every LDR # c gives a new state value to
the cell c as a function of cell states from the neighborhood N(c) of c. The action
of #
#(S) = #
c#C
S[S(c) # # c (S N(c) )], (10)
is the union of the states obtained by replacing the state of each cell c accordingly
to # c .
Hyperbolic Cellular Automata can be considered as a generalization of 'Cellular Au­
tomata', the main di#erence is our Hyperbolic Cellular Automata have non­regular
structure of the system of the cell neighborhoods. There is no a common template
of vicinity for cells, the neighborhoods of cells have variable cardinality and, hence,
the LDRs have variable arity. There are possible cases when c /
# N(c) and even
N(c) = {#}.
A hyperbolic cellular automaton # works as follows. If an initial state S 0 is given,
it iteratively applies the GDR # until it reaches a steady attractive state SA :
S 0
#
-# S 1
#
-# S 2
#
-# . . . #
-# SA .
The cells work synchronously in parallel governed by some global synchronization
signals.
4 From Iterated Function Systems to Hyperbolic Cellular
Automata
When we want to realize the dynamics of a digitized hyperbolic IFS
F = ((X, d), f 1 , f 2 , ..., f k )
4

with the help of a Hyperbolic Cellular Automaton #, we have the following picture.
As C, we take a regular lattice of some dimensionality m. In a practically interesting
case, m = 2 and C = {(i, j) | i = 1, . . . , p, j = 1, . . . , q}. The alphabet of states
A = {0, 1}. The cell neighborhoods are defined by the inverses of the IFS's functions
#c # C : N(c) =
k
#
i=1
f -1
i (c). (11)
The LDRs # c are the same for all cells c
#c # C : # c (S N(c) ) = # 1 if #c # # N(c) S(c # ) = 1
0 otherwise. (12)
We take as C the unit square S u of pixels and obtain the neighborhoods N(c) with
the help of our Algorithm described in [7].
The whole process of going from an initial IFS
F = ((X, d), f 1 , f 2 , ..., f k ) & F =
k
#
i=1
f i
to the corresponding Hyperbolic Cellular Automaton # looks like the following. Fist
of all we go to the dynamical system
((H(X), h), F ),
then, after digitization and scaling, to the dynamical system
((H(S u ), h), F ),
where S u is the unit square.
Eventually we construct the Hyperbolic Cellular Automaton
(S u , {0, 1}, N, A 0 , #) & N = #
s#S u
#
f#F
f -1 (s).
We start the dynamical process, beginning from a compact set A 0 # S u , and after a
big enough number M of iterations get an approximation AM of the IFS's attractor
A F :
# # : A 0 -# AM # A F .
5 Evolving Algebras
Evolving Algebras (known also as Abstract State Machines) have been proposed by
Yuri Gurevich in 1988 as models for arbitrary computational processes. They are
finite dynamic algebras representing state transitions and describing operational se­
mantics of discrete dynamical systems. They may be tailored to any desired level
of abstraction. System states are represented here as static algebras. Evolving Al­
gebras provide a formal method for executable specifications.
5

An evolving algebra is a structure
# = (#, S, I 0 , T ),
where # is a signature (a set of operational (or functional) symbols with their ari­
ties); S is a superuniverse (a union of all sorts), Boolean universe 2 # {0, 1} # S
(a universe (a sort) is represented by its indicator function U : S # 2); I 0 an initial
interpretation (a finite static many­sorted algebra); T a set of transition rules.
I 0 gives an initial interpretation of the signature's operational symbols:
I 0 : # # #
n#0
(S n
# S), I 0 (f) : S ord(f)
# S, #f # #.
NB: The interpretation I 0 (f) is a partial function on S n but it is total on the cor­
responding universes.
There are four kinds of transition rules (or updates):
1. Function updates
f(t 1 , . . . , t n ) := t 0 f # #, n # 0,
where t i are terms, the new function
f # # f [f(t 1 , . . . , t n ) # t 0 ]
2. Conditional
if b then C
3. Extension of universes
extend U # S by x 1 , . . . , xm
4. Contraction of universes
discard t from U
Iterative application of evolving algebra # to sequentially arising states (static alge­
bras) I i , starting from the initial state I 0 , may give a terminated computation
I 0
#
-# I 1
#
-# I 2
#
-# . . . #
-# I M .
6 Hyperbolic Cellular Automata as Evolving Algebras
It is pertinent to note that there may be several approaches to using Evolving
Algebras for specification of Hyperbolic Cellular Automata. In the simplest case
of one Hyperbolic Cellular Automaton one can directly go from its mathematical
definition and a given IFS to an Evolving Algebra. When it is required to construct
6

an IFS and the corresponding Hyperbolic Cellular Automaton, some complications
arise associated with the need to appeal to some second order constructions. As the
first step on the way of applying Evolving Algebra formalism to Hyperbolic Cellular
Automata we give here a sketch of an Evolving Algebra for a Hyperbolic Cellular
Automaton. Instead of speaking in terms of superuniverse it is convenient to use
specific sorts (i.e. their indicator functions), and to extend the LDRs # c onto the
whole set of cells
” # c (c) = undef, #c /
# N(c).
The information of the IFS under consideration is reflected in the set of neighbor­
hoods. The initial interpretation is given for the 2D­case.
. Sorts
-- Cells
-- Attributes
-- {N c | c # Cells} (set of neighborhoods)
-- undef
. Static Functions
-- {delta c : Cells # Attributes | c # Cells & delta c(c) = undef, #c /
# N c}
. Dynamic Functions
-- State : Cells # Attributes
. Transition Rules
-- {State(c) = delta c(c) | c # Cells}
. Initial Interpretation
-- Cells # {(i, j) | i = 1, . . . , p; j = 1, . . . , q}
-- Attributes # {0, 1}
-- # N c # {0, 1} {(i,j) | i=1,...,p; j=1,...,q}
| c # Cells #
-- {delta c : {(i, j) | i = 1, . . . , p; j = 1, . . . , q} # {0, 1}}
-- {State : {(i, j) | i = 1, . . . , p; j = 1, . . . , q} # {0, 1}}
7 Conclusion
Hyperbolic Cellular Automata were designed for constructing fractal objects but
they are in their own right. Evolving Algebra specifications are mathematically
well founded and directly executable. In the talk, an Evolving Algebra approach
to formal description of Hyperbolic Cellular Automata has been outlined. At least
two steps of further study should be mentioned. The first one is to develop a way
for specification of variable Hyperbolic Cellular Automata. The second one is to
give an Evolving Algebra specification of our Algorithm of constructing a HCA for
a given IFS [7].
7

References
[1] McCulloch W., Pitts W., A Logical Calculus of the Ideas Immanent in Nervous
Activity, Bull. Math. Biophysics, 5, 1943, 115­133.
[2] Ulam S., On Some Mathematical Problems Connected with Patterns of Growth
of Figures, in Essays on Cellular Automata, A. W. Burks (ed), Univ. of Illinois
Press, 1970, 219­243.
[3] Von Neumann J., Theory of Self­Reproducing Automata, A. W. Burks (ed),
Univ. of Illinois Press, Chicago, 1966.
[4] Von Neumann J., The General and Logical Theory of Automata, in Hixon
Symposium Proc., 1948 in J.N. Neumann Collected Works, A.H. Taub (ed),
Pergamon Press, New York, Vol. 5, 288­328, 1963.
[5] Goles E., Martinez S., Neural and Automata Network: Dynamical Behavior
and Applications, Kluwer Academic Publishers, Dordrecht, 1990.
[6] Barnsley, M. F.: Fractals Everywhere. Springer­Verlag, Berlin, 1986
[7] Severyanov, V. M.: Automata Network Dynamical Systems for Construction of
Fractal Objects. Mathematics and Computers in Simulation 57 (2001) 317­324.
[8] Severyanov, V. M.: Parallel Computation of Fractal Sets with the Help of
Neural Networks and Cellular Automata. In: Parallel Computing Technologies,
Proc. IV Int. Conference, PACT­97, Yaroslavl, Russia, September 1997, ed. B.
Victor Malyshkin, Springer­Verlag, Berlin, 1997, 109
[9] Barret, C. L., Reidys, C. N.: Elements of a theory of computer simulation I:
Sequential CA over random graphs. Applied Mathematics and Computation 98
(1999) 241­259.
[10] Yuri Gurevich: Logic and challenge of computer science. In E. B˜orger, editor,
Specification and Validation Methods. Oxford University Press, 1995
[11] Yuri Gurevich: Evolving Algebras: a tutorial introduction. Bulletin of the Eu­
ropean Association for Theoretic Computer Science, 43:264­284, 1991
8