D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction

7.5.

Asynchronous

Automata Networks

221

for

alFn

> 1.

Note that

we are

using

a

discrete model

of

time. Thus

the

successive states

of

the

local automaton

A

v

at

node

v,

a

v

(0),

a

v

(l),

a

v

(2),...

and the

successive global states

o(O),

a(l),

a

(2),...

of the

entire network

A

depend

in

general

on the

particular values

of

external inputs,

except

in the

case

\X\ = 1. The

function

a : N -> A

with a(n) having

u-component

a

v

(n)

e A

v

is

called

the

behavior

of the

synchronous network

A on the

given

input sequence

{.x,,}

we

N

and

initial state

a(0).

Note also that

in

this synchronous case,

a

letter

is

read

at

each update,

so the

wait

symbol

is

never used

in

place

of an

input letter

by any

feedback

function

<p

v

.

Thus

we

could have equivalently used

X

rather than

X

9

in the

definition

of the

<p

v

.

This

is

what

the

classical definition does.

X® is

needed

for the

general asynchronous case below.

In the

synchronous case and,

as we

shall

see,

for

generalized cellular automata, this

is

equivalent

to the

classical definition.

Our

concept

of

asynchronous

automata

network

A

requires again giving

a

digraph

T>

= (V, E), a

V-indexed

set of

automata

A

v

, an

external input alphabet

X, and a V-

indexed

set of

feedback

functions

{(p

v

}

v

^v

that

are

compatible with

A

V-indexed

family

of

read

functions

which

are

used

to

determine whether

the

feedback

function

for

node

v

receives

the

wait

symbol

9 or a

letter

of

external input,

is

also

required.

These

ingredients

completely

determine

the

asynchronous automata network

A.

We

will allow local update

at a

node

v

without necessarily changing

local

state

at

any

other node,

and

local automata will

be

allowed

to

read

the

global input sequence

asynchronously

and

independently according

to

their update times

and

local state

in

their

neighborhoods.

In

particular,

local

automata will

be

allowed

to

wait

(as a

function

of the

state

of

their local neighborhood) before reading

the

next letter

of

external input.

To

capture

the

notion

of

asynchronous

local

updates, embed

N as a

model

of

time

arbitrarily into

the

nonnegative real numbers

R

+

(or

nonnegative rationals

Q

+

, or N),

with

r(0)

=0 and i < j

implying

r(i)

<

T(J).

At

time

t(ri)

with

n

positive,

a set of

local updates will occur simultaneously

in the

asynchronous automata network. During

the

half-open interval

[0,

r(l)),

the

state

of the

automata network

is an

initial

global state

a(0)

as

above.

For

each

n > 0,

during open interval (r(n),

r(n +

1)),

the

state

of the

network

does

not

change

at

all.

At

time

r(n),

let

U

T

(

n

)

^ V

denote

the

nodes

updated

at

time

r(n).

Formally,

a

(local)

update

is

said

to

occur

at

node

v 6 V at

time

r(n)

e R

+

if

and

only

if v

lies

in the

update

set

U

r

(

n

).

Thus subsets

of the

local

automata

of A

will

be

updated instantaneously

at

time points

r(l), r(2), ...,

with

all

local

automata having

nodes

in the

update

set

U

T

(

K

)

updated simultaneously

as a

function

of the

current states

of

their neighbors

and

possibly

the

input letters they

are

currently reading.

We

require that

each node

v e V is

updated

an

unbounded number

of times,

i.e.,

v €

U

r

(

n

)

for

infinitely

many

n e N.

An

update

pattern

(T, V) of an

asynchronous network

is an

order-preserving function

(as

above)

T : N ->• R

+

together with

a

family

of

update sets

U

T

(

n

)

V,n > 0.

(Sometimes

we

will suppress

the

update sets

and

refer

to r as an

update pattern.)

For t e R

+

\

r(N)

222

Chapter

7.

Finite

State-Homogeneous

and

Asynchronous

Automata Networks

and

also

for t = 0, one may

define

U

t

= 0.

Then

for all

moments

in

time

t e R

+

, an

update

occurs

at

node

v at

time

t if and

only

if v e U

t

. A run of a

network

is a

sequence

of

global

states a(t)

of the

network,

and we

will soon

see how an

update pattern together with

a

infinite

input word

[x

n

}

n>

o

(with

x

n

in X for all

positive natural numbers

n)

determine

a

well-defined

run a : E

+

-> A,

with component values #„(?)

=

(o(O)u

e A^ at

time

t e R

+

,

called

the

(continuous)

behavior

of the

asynchronous network

A for

this update

pattern

and

input sequence, with initial global state a(0).

The

restriction

a :

r(N)

-» A,

of

a to

r(N),

is

called

the

(discrete)

behavior

of ^4 and

clearly determines

the

continuous

behavior

a on R

+

,

since nothing

in the

network

may

change

at any t g

r(N).

An

update

pattern

is not a

part

of the

specification

of the

automata network

and

need

not be

given

in

advance.

An

update pattern

and

external input sequence are, however, required

to

determine

a

behavior

of the

network.

Local

Reading

and

Waiting.

For

each node

v e V, we

assume

a

next available

letter

*„*(„)

€.

X—which

one

will

depend

on how far A

v

has

read(!)—is

available

at

time r(n)

to

be

read

from

the

sequence

of

global external inputs

x\, *2,

£3,... which

are

read sequentially

but

not

synchronously

by the

local

automata

in the

asynchronous network. That

is, the

letters

of

external input

x\,

X2,

x$,...

are

read

in

sequence

at

each node

v, but

node

v is

also permitted

to

wait

and

update itself before reading

(or

"consuming")

a

letter.

This

is

why

the

feedback

function

must handle

the

case when

the

next letter

is not to be

read yet,

i.e.,

<p

v

: A x X

s

-» X

v

,

where

5, the

wait symbol,

is

used

as the

second argument

to

tp

v

when

the

next input

letter

is not

read.

However, whether

the

next letter

at

node

v is

read

may

depend

at

most

on the

states

of

the

local

automata

at the

neighbors

of

node

v and may not

depend

on

external input

letter

itself. Thus this

is

determined,

for

each node

v e V, by the

read

function

p

v

:

YlweN(v)

AW

-»•

{0,1}

for

node

v.

Like

the

feedback

functions

tp

v

,

the p

v

are

given when

specifying

the

asynchronous automata network

and may be

extended

to all

global states

p

v

: A ->

{0,1}

by

defining

Thus

p

v

(a) does

not

really depend

on the

w-component

a

w

of a € A

unless

w e

N(v).

If

p

v

(d)

= 1

when

v e

U

r

(

n

),

then

the

next external input

letter

is

read

and

passed

to

the

feedback

function

<p

v

;

but if

p

v

(a)

= 0

when

v €

U

T

(

n

),

then

the

wait symbol

9 is

passed

to the

feedback

function,

and the

external letter remains available. Letters

of a

copy

of

the

infinite

external input sequence

are

thus consumed

in

order

at

every node. Each

local

automaton gets

to

consume

a

copy

of the

same external input sequence,

but the

local

automaton

may

wait before consuming

the

next letter, depending

on the

state

of its

local

neighborhood

and the

function

p

v

.

Thus

at

time

t =

r(n) with

n > 0, if v e

U

T

(

n

)

and the

locally available

for

reading

is x e X, a

local

update

of

state

at

node

v is

given

by

Note that

the

values

of

<p

v

and p

v

here

do not

depend

on the

state

of

local

automata

other than

the

neighbors

of A

v

at

time

r(n — 1).

Since

p

v

is a

function,

there

is no

non-

determinism

in

deciding whether

the

next letter

is to be

read

or not for a

given state

a e A.

7.5.

Asynchronous

Automata Networks

223

Details

of

Asynchronous

Behavior.

To

keep track,

as

external observers,

of

which letter

of

the

external input sequence

is

currently available

at

time

r (n) at

node

v, we

note that

the

index

n*(v)

to the

for

node

v at

time

r(«)

is

given inductively

by

l*(v)

= 1 and

Thus, starting

from

the first

letter

of the

global input sequence

{*

n

}n6N

+

>

the

index

to

the

next input letter

is

advanced

if and

only

if the

input letter

in

position

n*(u)

has

been

read when

A

v

was

last updated. Thus

the

letter which

may be

read

by the

local

automaton

at

node

v e V at

time r(n), with

n a

positive natural number,

is

denoted

*n*(u)

€ X.

Up

to but not

including time T(«),

the

local

automaton

at v

will have consumed

x\,...,

jc

n

*(

v

)_i.

Thus

*„.(„)

indicates

the

that

the

local

automaton

may

consume

at

time r(h).

It is

important

to

note that

the

local

automata

A

v

do not

themselves carry

any

information

on

what

the

next letter will

be or

where

to find it, any

more than

do

standard

finite

automata

reading

an

input sequence.

The

notation

jc

w

*(

v)

merely allows

an

external

observer

to

describe which

is the

next letter

of the

external input sequence that

is

available

to

the

local automaton.

The

updates

of

state

at

node

v for n > 0 are

formally described

by

where

*„*(„)

e X is the

letter

in

position n*(u)

of the

external input sequence.

Recall that

no

change

of

state occurs

at

time

t

unless

t =

r(n)

for

some

n > 0.

Therefore

at

every node

v e V, for all

times

r in the

half-open interval [r(n

—

1),

r(n)),

where

n > 0, we

have a

v

(t)

=

a

v

(x(n

—

1)). Thus

the

state

of

node

v

during this interval,

i.e.,

the

state

from

time r(n

—

1) up to and

including

any time

just before

time

r(n),

is

exactly

a

v

(r(n

—

1)). Given

an

initial

global state a(0),

the

above update rule determines

the

state a

v

(t)

of A

v

and

hence

the

state a(t)

of the

entire network

for all t e R

+

, so we

have

a

well-defined run,

the

(continuous) behavior

of A.

Note

that

if

external inputs

are

always read (i.e., p

v

(a)

= 1 for all a e A, v e V) and

U

r

(

n

)

= V

foreveryn

> 0,

then

the

sequence

of

global states

a(r(0)),a(r(l)),a(r(2)),...

is

exactly

the

behavior

of a

uniquely determined corresponding synchronous automata

network.

To

state

our

main result,

we

introduce notions

of

spatial-temporal covering

and of

asynchronous emulation (related

to the

notion

of

isomorphic simulation

for

automata).

39

A

spatial-temporal

covering

for

digraph

D is any

function

A,

: R

+

x V -> N

such

that

following conditions hold:

(1) The

restriction

A :

M.

+

x [v] -» N of

A.

to

every given vertex

v e V is

surjective.

39

More

general

definitions

of

emulation allowing

differing

sets

of

nodes

and

alphabets

for A and A,

partial

definition

of it,

etc.,

are

possible

(in

analogy

to the

classical notion

of

division

for

synchronous automata),

but

for

simplicity

we

shall

use

this one, which

suffices

for our

purposes here.

224

Chapter

7.

Finite State-Homogeneous

and

Asynchronous Automata Networks

(2)

A is

locally monotonically increasing, i.e.,

for all t, t' e R

+

and v e V,

(3)

For all t, t' e R+ and v € V,

where

d

denotes

the

distance

metric

in the

associated

digraph

T>

(the reflexive-symmetric

closure

of the

relation

E)•

Let

A be an

synchronous automata network over

a

digraph

= (V, E)

with

global

state

set A, and let A be an

asynchronous automata network with

the

same input alphabet

X,

a

digraph

T>'

= (V, E')

with

the

same

set of

nodes,

and

global

state

set A. Let

TT

: A

—>

A

be a

function from

global

states

of the

asynchronous automata network

to

global states

of

the

synchronous one, such that

(a) =

(n(a))

v

depends only

on a

v

for all a e A.

Thus

we

can

denote (n(a))

v

by

n(a

v

).

^

We

then

say

that

the

behavior

a : E

+

->• A of A

starting

in

state a(0)

for

update

pattern

(r, U) ami

input

sequence

x\,

*2,...

(*, € X for / € N)

emulates

the

behavior

a

: N -> A of A

starting

in

state a(0) with

the

same input sequence under

the

projection

n if

there

exists

a

spatial-temporal

covering

A.

: E

+

x V -» N

such that

the

following

diagram commutes

for

each

v € V:

That

is,

7r(flj,(0)

=

a

v

(k(t,

v))

with a

v

(n)

=

state

in A of

node

v at

time

n e N and

a

v

(t)

=

state

in A of

node

v at

time

t € R

+

.

Theorem

7.22

(asynchronous

emulation

of

synchronous

automata

networks).

Let

any

synchronous automata network

A

over

a

locally

finite

digraph

T>

= (V, E)

with local

automata

A

v

=

(A

v

, X

V

,S

V

)

(v e V) and

external input alphabet

X be

given.

We

construct

an

asynchronous automata network

A

(with

the

same input alphabet

X)

such that every possible behavior

of

A

with input sequence [x

n

}

n>

o emulates

the

(only

possible) behavior

of

A

with input sequence

[x

n

}

n>

Q,

when

A

starts

in an

initial global

state

a (0)

depending only

on the

initial global state a(0)

of

A.

Moreover,

the

following hold:

(1) The

underlying digraph

for A is the

reflexive-symmetric

closure

of

the

digraph

for

A

(2) For

each vertex

v, the

local automaton

A

v

of

A are not

much more complicated than

the

local automaton

A

v

of

A.

Moreover,

A

v

is a

direct product

of

A

v

, an

identity-

reset^automaton,

and a

modulo three counter (with identity).

40

In

fact,

A

v

has

state

set

A

v

= A

v

x A

v

x {1, 2, 3}.

^Recall

that forn

> 1, a

modulo

n

counter with identity

is an

automaton

C\ =

({1,...,

n},

{+0, +1}, S

c

\)

with

S

c

i (i, +1) = i + 1

(rnodn),

and &

c

\ (i, +0) = i, i =

1,...,

n.

7.5.

Asynchronous

Automata Networks

225

(3)

The

projection

TT

: A

—>•

A is

given

locally

by

n

v

(a

v

,

b

v

, r) =

a

v

for (a

v

,

b

v

, r) € A

v

.

(4) The

starting

state

of

A is

given

by

a

v

(0)

=

(a

v

(Q),

a

v

(ty,

3) for all v e V.

(5)

Furthermore,

the

spatial-temporal

covering

of

the

emulation

satisfies

We

call

X.(t,

v) the

local

time

of the

synchronous automaton

A at

vertex

v for

time

t

in the

emulating asynchronous automaton

A. Of

course,

A

depends

in

general

on the

update

pattern

(T, (7) for the

particular behavior

of A.

Thus

(5)

above says that

the

difference

in

local

time

at two

nodes

in the

emulating asynchronous automata network

is

bounded above

by

approximately one-third

the

distance between them.

Proof.

We

give

the

construction

of A and

show

by a

series

of

lemmas that

it

hasthe required

properties.

As

before,

let

T>

be the

reflexive

and

symmetric closure

of

T>.

D = (V, E),

where

Let

N(v~)

denote

the

neighborhood

of v in

T>.

We

construct

A as an

automata network over

T>.

The

local

automaton

A

v

at

node

v e V has

states

A

v

— A

v

x A

v

x {1, 2, 3}, and its

input alphabet

is

where

1 is a new

symbol that acts

as the

identity

on the

corresponding component, and,

for

each

a

v

e A

v

, the

middle component includes input letter

constant

a

v

,

which acts

as a

constant resetting

the

middle component

to a

v

,

whereas,

in the

third component,

+0

acts

as

the

identity

and +1

increases that^component

by 1

modulo 3.

41

We

write

a

v

=

(a

v

,

b

v

, r

v

) e A

v

= A

v

x A

v

x {1, 2, 3} for the

local state

a

v

at

node

v

€ V of A. The

read

functions

of A are p

v

: A -+

{0,1} with

The

feedback

functions

of A are

<p

v

: A x X

9

-> X

v

with

41

The

asynchronous construction here uses

a

modulo

n

counter

for the

third component

of

local state with

n

= 3, but

with obvious modifications

n > 3

could

be

used just

as

well.

The

reader

may

observe that

the

method would

not

work with

n — 2.

Intuitively,

the

construction relies

on

being able

to

locally distinguish

whether neighbors

are in the

future, present,

or

past relative

to a

given node

(in the

corresponding synchronous

network). Thus,

at

least

three values

are

required. Having these distinctions

in the

asynchronous realm,

we

can

guarantee that

local

time never gets

too far

"out

of

sync"

for

nearby

nodes,

as we

shall establish formally.

226

Chapter

7.

Finite

State-Homogeneous

and

Asynchronous

Automata Networks

where

a

v

is the first

component

of a

v

in

state

a and c is an

arbitrary state

of A

such that

for

each

w e

N(v),

Note

also

r

w

must

lie in {1, 3} in the

determining

the c

w

of the

third case,

as

necessarily

r

v

= 3 in

third case

and w e

N(v)

c

N(v) implies

r

w

^ 2

(mod

3).

Updates

at

node

v in A are

thus given

by the

local update

function

with

where

c is as

above.

That

is,

if

r

w

= r

v

— 1

(mod

3) for

some

w e

N(v),

if

r

w

^ r

v

— 1

(mod

3) for all w e

N(v)

and r

v

^ 3,

otherwise,

where

c is as

above.

Notice that

the

transition

function

of A

v

and the

feedback

function

p

v

from

the

synchronous network

are

used

to

give

the

input

to A

v

in the

third

case.

Of

course

the

value

of

a

v

•

(p

v

(c,

x)

depends only

on x, a

v

and the c

w

with

w in

N(v),

the

neighborhood

of v

in

the

original digraph

V.

In

computing

8

V

, x e X

s

is the

letter currently available

for

possible reading

by the

local automaton

at

node

v if

p

v

(a)

= 1 but is x = 3 in

case ^(a)

= 0

(see

the

discussion

of

local

reading

and

waiting above).

By our

choice

of

reading

functions,

the

letter

x is the

wait symbol

9 in the first two

cases

of the

local update rule

and

lies

in X if and

only

if the

third case applies.

42

Thus,

the

third case applies

if and

only

if the

next available letter

is

consumed.

Suppose

the

initial state

of A in a

synchronous

run is

0(0) with each node

v £ V

in

state a

v

(Q)

e A

v

. Let the

initial state

of A

have

the

automaton

at

each node

v in

state

fi

B

(0) =

(fl

B

(0),fl

w

(0),3).

For a

given behavior

of A, we say

there

is a

-\-l-update

at

vertex

v

whenever

the

transition rule

8

V

is

applied

to

update

the

local state using either

its

second

or

third case, i.e.,

exactly when

the

last component

of

state

is

incremented

by -f 1

modulo

3. We say

there

is a

real

update

at

node

v

(corresponding

to a

synchronous update

in A at

that node) whenever

42

If

X is a

singleton,

the

above definition

of S

v

is

even consistent with p

v

(a)

= 1 for all a € A,

since

the

current

letter

is not

different

from

the

infinite

input word consisting

of

identical

letters.

This

observation will

be

used when

we

specialize

Theorem 7.22

in

Corollaries

7.29

and

7.30, respectively,

to

emulating

generalized

cellular automata

and

cellular automata

by

asynchronous automata networks which

can

be

chosen

to be

asynchronous generalized cellular automata

and

asynchronous cellular automata, respectively.

7.5.

Asynchronous

Automata

Networks

227

transition rule

8

V

is

applied

to

update

the

local state using

its

third case, i.e., exactly when

the

last component

of

state changes

from

3 to 1. Let

p(t,

v) be the

number

of

+l-updates

that have occurred

at

vertex

v

during

a

behavior with update pattern

T up to and

including

time

t e R

+

.

Lemma

7.23.

For

each pair

of

neighboring

nodes

v, v

f

€ V in

T>

and

for all t e E

+

,

Proof.

It

suffices

to

consider

the

values

of p(t , v) for t €

(r(0),

T

(1), r(2),

r

(3),

. . .}

since

no

applications

of

local

transition

rules

occur between them.

At t = 0 =

r(0),

p(t , w) = 0

for

all w

eV,sop(t,v)

=

p(t,

i/)

holds.

Now by

induction,

we

suppose that

the

inequality

holds

at

time r(k)

for all k < n e N.

If

p(r(n),

v) =

p(r(n),

v

1

), then

at

time

n + 1, a

+l-update

will occur

at

none, one,

or

both

v and v', so, as a

result,

the

inequality will always hold

at

time

i(n + 1).

Otherwise \p(r(n), v)—p(r(ri),

t/)|

= 1.

Without loss

of

generality,

we may

assume

Since

the

last component

of

state

at a

node

is

increased

by 1

(modulo

3) for

each

+1

-update

at

that node

and

otherwise remains unchanged, obviously

the

last component

r

w

(t) of

state

at

any

node

w in V is

congruent

to p(t , w}

modulo

3.

Therefore

It

follows

from

the

definition

of

local update

8

V

that there will

be no +1

-update

at

node

v

at r(n + 1), so

p(i(n),

v) =

p(r(n

+ 1), v). Now

there

are two

possibilities:

Either

there

is

also

no

+l-update

at

node

v' at

this time,

so

p(r(n),

v') =

p(r(n

+ 1), v') and the

inequality

is

preserved;

or,

otherwise, there

is a +1

-update

at

node

v', so

then

and

again

the

inequality holds.

It

follows

by

induction that

it

holds

for all n, and

hence

for all t e R

+

. n

Corollary 7.24.

Let v and v' be

vertices

at

distance

d in the

graph

D.

Then

for all t € R,

Proof.

This follows immediately

by

considering

a

path

of

minimal length

from

v to v' and

applying

the

above lemma.

Define

A(f,

v) to be the

number

of

real updates that have occurred

at

node

v in A up

to

and

including time

t e

1R

+

.

Corollary

7.25

(continuity

of

local time).

Let v and v' be

vertices

at

distance

d in the

graph

P.

Then

for all t € R

+

,

228

Chapter

7.

Finite

State-Homogeneous

and

Asynchronous

Automata Networks

Proof.

By

definition

we

have

We

may

assume .(t,

v)

.(f, v'), whence

Since

(t, v) —

A.(f,

i/)|

is an

integer,

it can be no

more than

•

Lemma 7.26 (freedom from

deadlocks).

With

asynchronous

automata network

A in the

initial

configuration

with a

v

(0)

=

(a

v

(0),

a

v

(0),

3)

corresponding

to an

initial

configura-

tion

of

A

with

node

v e V in

a

v

(0),for

any

update

pattern

( , U) and any

input

sequence

{x

n

}n>o

of

letters

in X, the

number

of

real

updates

at

each

node

is

unbounded.

That

is, for

each

fixed v € V,

always

It

follows

that

: R

+

x [v] ->• N is

surjective

for

each

v V.

Proof.

It

suffices

to

show,

for

each

fixed v =

VQ

e V, p(

(n),

VQ)

increases without

bound.

Hence

it is

enough

to

show that

if p(

(n),

VQ)

= R,

then there

is an r > n

with

p(

(r),

V

0

)

>^R.

Since

D is

locally

finite,

there

are finitely

many nodes

V

0

,

v

1

,...

V

k

with

distance

d(v

o

,

v

i

) < R. By our

hypotheses

on

update patterns each

of

these

v

t

e U (

m

) for

infinitely

many

m > n.

Suppose,

for a

contradiction, that

no

node among these

can

receive

a+1-update.

That

is,

for all m > n, p(

(n), v

i

,)

= p(

(m),

v

i

) for all 0 < i < k. Let

w(0)

=

VQ.

Inductively,

starting with

i = 0,

since iu(i) cannot

get a

+1-update,

by

definition

of ,

w(i) must have

a

neighbor

Wi(i+l)

with

r

w

(i+1)

=

r(i)

-1

(mod

3)—

1

(mod

3), and

hence

by

Lemma 7.23,

p(

(n), w(i+

1))

= p(

(n), w(0)

—

1.

Thus

we can find

distinct nodes, w(0), w(l), u;(2),..., w(R)

within

distance

R of

node

v =

w(0)

such that

p(

(n), w(/))

= p(

(n),

v)

—

i for 0 i

R. In

particular

the

node w(R)

has p(

(n), w(R))

= 0. By

Lemma 7.23,

the

neighboring

nodes

w' to

w(R) have

p(

(n),

w') {0, 1}, and 0 < p(

(m'),

w) < 1 for all m' > n

as

long

as

w(R)

has not

received

a

+1-update.

Let m > n be the

least integer, such that

w(R)

€ U

(

m

). Then

by the

local

update rule, w(R) gets

a

+l-update

at

time r(m)

but

lies

with distance

R of

VQ,

a

contradiction.

Therefore,

within

the finitely

many nodes within distance

R of v,

some node must

indeed

be

+l-updated

at

some time r(m) with

m > n.

Repeating this argument,

for

any

time

r(n'),

we can

always

find a time

r(m') with

m' > n'

such that some node within

distance

R of

VQ

gets

a

+1-update.

Since there

are

only

finitely

many such nodes, eventually

(for

some

r > n)

some node

w =

t>,

(0 < i < k)

among them will have

p(

(r),

w) > 2R.

7.5.

Asynchronous

Automata Networks

229

But

then

by

Corollary 7.24,

implying

that

i.e., node

VQ

must

get a +1

-update

as

well.

The

local tune

function

A

is

clearly locally monotonically increasing,

so

Lemma 7.26

and

Corollary 7.25 (together with

the

fact

that

[^

J

< d

show that

X

is a

spatial-temporal

covering,

as

required.

Proposition

7.27 (emulation using

local

time).

Let the

initial

states,

inputs,

and

update

pattern

be as in

Lemma 7.26.

Then

the first

component

of

state

at

node

v in the

asynchronous

automata

network

A at

time

t

equals

the

state

of

node

v in the

synchronous

automata

network

A at

time

k(t,

i>).

That

is,

Proof.

It

suffices

to

prove

the

assertion

for all t e

r(N).

If

a

v

(t)

— (x, y, r) e A

v

,

then

let

n(a

v

(t))

= x, its first

component

as

before;

let

7*2

(0v

(0) = v, its

second component,

and let

r

v

(t)

= r, its

third component.

We

proceed

by

induction

on m to

show that

(2)

A.(r(m),

u) > 1

implies that 7r2(a

r

(r(m)))

=

a

v

(X(r(m),

v)

—

1),

(3)

m > 0

implies that

m*(u)

=

A(r(m

- 1), u) + 1.

We

first

carry

out the

induction

for

(3).

If m = 1,

then

by

definition l*(v)

= 1, but

since

at

time r(0)

at v

there have been

no

real updates,

we

have A(r(0),

u) +1 = 1. For m > 1,

by

definition

m*(u)

= (m

—

l)*(v)

+ 1 if and

only

if v e

£/

T

(

m

)

and

p

v

(a(r(m

—

1)))

= 1,

i.e.,

if and

only

if the

third case

in the

definition

of

8

V

is

applied. Thus

m*(i>)

increases

if

and

only

if

there

is a

real update

at

node

v;

i.e., every time

A.(r(m

—

1), v)

increases

by 1,

so

does

ra*(u).

Thus,

This

and the

induction hypothesis yields (3).

For

m = 0, we

have r(0)

= 0,

X(r(0),

u) = 0 and

a«(0)

=

(a

v

(0),

0

V

(0),

3), so (1)

is

immediate.

(2)

holds vacuously.

Suppose

by

induction hypothesis that

(1) and (2)

hold

for all m

with

0 < m < n. We

show

that these assertions

follow

also

for m = n.

Case

1. If v €

U

r

(ri)

but

there

is no

real update

at

node

v, it

follows

from

the

definition

of

A.

that

X(r(«),

v) =

X(r(n

—

1), v)

and, using

the

definition

of

V

that

the first

and

second coordinates

of a

v

are

unchanged. Thus, n(a

v

(r(n)))

=

n(a

v

(r(n

—

1))),

and

therefore

230

Chapter

7.

Finite State-Homogeneous

and

Asynchronous

Automata Networks

as

required

for

(1).

For

implication (2),

if

A(r(n),

v) > 1,

then

(a

v

(r (n)}}

=

n2(a

v

(r(n

—

1)))

as

second component

is

unchanged,

=

a

v

(k(t(n

— 1), v) — 1) by

induction hypothesis,

=

a

v

(k(r(ri),

v)

—

1)

since

A(r(n),

*>)

=

A(r(n

—

1), u),

as

required.

If

A.(r(n),

v) = 1,

then

it is

clear

from

the

definition

of 8

V

,

since

the

value

of

the

second coordinate

can

only

be

changed

in

Case

3,

below, that 7^(0,, (r(n)))

=

a

v

(Q),

which

is

just a

v

(X(r(n),

u)

—

1), as

required.

Case

2.1fvg

U

T

(

n

),

then

a

v

is

unchanged

and

everything follows

as

above.

Case

3.

Finally,

if v e

T

(n)

and

there

is a

real update

at v at

time r(n), then

by

definition

of S

v

we

haver,; (r(n

—

1)) =

3andr

w

(r(n

—

1)) ^

r

v

(r(n

— 1))

—1

(mod3)for

all w €

N(v), where r

w

(t) denotes

the

third component

of

a

w

(t).

So

each

r

w

(t(n

— 1)) G

{1,3}.

It

also

is

clear

by

induction that r

w

(t)

=

p(t,

w)

(mod

3)

always holds.

By

Lemma

7.23, \p(t,

w) —

p(t,

u)| < 1 for the

neighboring nodes

w and v.

We

consider

the

c

w

's that

are

used

in the

third

case

of the

local update rule

in

updating

node

v.

If

r

w

(t(n

— 1)) = 3,

then p(r(n

— 1), w) =

p(r(n

— 1), v)

follows

and

hence

A(r(n

— 1), w) =

k(r(n

— 1), u). In

this

case,

by

induction hypothesis

for

node

w,

7i(a

w

(t(n

—

1)))

=

a

w

(A(r(n

—

1), w)} =

a

w

(X(r(n

— 1),

u)).

It

follows that

c

w

in the

third case

of the

local

update rule equals a

w

(X(r(n

— 1),

u)).

Otherwise,

r

w

(r(n

— 1)) = 1, and

since

r

v

(r(n

— 1)) = 3,

wehave/?(r(n

—

1), w) =

p(r(n

- 1), v) + 1

and

hence X(r(n

- 1),

w)

=

X(r(n

- 1), v) +

I.

43

Thus

A.(r(n

—

1), w) > 1, and so

then

c

w

=

Jt2(a

w

(T(n

-

1))) since

r

w

(r(n

- 1)) = 1,

=

a

w

(X(t(n

— 1), w} — 1) by

induction hypothesis

at

node

w,

=

a

w

(X(T(n

- 1),

w)).

It

follows that

for

each

u; e

N(v),

the

Cu,

in the

third case

of the

local update rule applied

at

node

v

equals

a

w

(k(r(n

— 1),

u)).

By

the

induction hypothesis that n(a

v

(T(n

—

1)))

=

a

v

(^(r(n

— 1), u)) and by

(3),

n*(u)

=

A.(r(n

—

1), u) + 1.

Thus,

the first

component

of

a

v

(z(ri)}

is

43

Notice

that

the

most recent

+l-update

at

node

w

must have been

a

real update, since

r

w

(r(n

— 1)) = 1.

Since

r

v

(r(n

—

1)) = 3 and

nodes

v and w

differ

by at

most

one

+l-update,

local time

at

node

v is

behind

local time

at

node

w by

exactly

1.

D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction

Подождите немного. Документ загружается.