D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
Bibliography
251
A.
Salomaa
[1960b],
On the
Composition
of
Functions
of
Several
Variables
Ranging
over
a
Finite
Set. Ann. Univ. Turkuensis Ser. AI41, Turku, Finland, 1960.
A.
Salomaa [1962],
Some
Completeness
Criteria
for
Sets
of
Functions
over
a
Finite
Domain.
Ann.
Univ.
Turku
Ser. A153, Turku, Finland, 1962.
A.
Salomaa [1963a],
On
Basic
Groups
for the Set
of
Functions
over
a
Finite
Domain. Ann.
Acad. Sci. Fenn. Ser.
AI338,
Helsinki, Finland, 1969.
A.
Salomaa
[1963b],
On
Essential
Variables
of
Functions,
Especially
in the
Algebra
and
Logic.
Ann. Acad. Sci. Fenn. Ser.
A1339,
Helsinki, Finland, 1963.
A.
Salomaa
[1969],
Theory
of
Automata.
Pergamon Press, Oxford, U.K., 1969.
A.
Salomaa
[2003],
Composition sequences
for
functions
over
a finite
domain.
Theoret.
Comput.
Sci.,
292
(2003),
263-281.
M. W.
Shields [1987],
An
Introduction
to
Automata
Theory.
Blackwell Scientific Publica-
tions,
Oxford,
U.K., 1987.
M.
Simon [1999], Automata
Theory,
World Scientific, Singapore, 1999.
A. R.
Smith,
III
[1971], Simple computation-universal cellular spaces.
J.
Assoc.
Comput.
Machinery,
18
(1971)
339-353.
M.
Steinby
[1969],
On
Definite
Automata
and
Related
Systems.
Ann. Acad. Sci. Fenn. Ser.
AI444, Helsinki, Finland, 1969.
J.
Stoklosa [1977],
On
operation preserving
functions
of
shift
registers.
Found.
Control.
Engrg.,
2
(1977),
211-214.
T.
Sudkamp
[1988],
Languages
and
Machines.
Addison-Wesley, Reading, Mass., 1988.
T.
Sudkamp
[1997],
Languages
and
Machines:
An
Introduction
to the
Theory
of
Computer
Science,
2nd ed.
Addison-Wesley Longman, Inc., Reading, Mass., 1997.
M.
Tchuente [1979], Parallel calculation
of a
linear mapping
on a
computer network. Linear
Algebra
Appl,
28
(1979),
223-247.
M.
Tchuente
[1982],
Parallel realization
of
permutations over trees.
Discrete
Math.,
39
(1982),
211-214.
M.
Tchuente
[1983],
Computation
of
Boolean
functions
on
networks
of
binary
automata.
J.
Comput.
System
Sci.,
26
(1983),
269-277.
M.
Tchuente
[1985],
Permutation factorization
on
star-connected networks
of
binary
automata.
SIAM
J.
Algebraic
Discrete
Methods,
6
(1985),
537-540.
M.
Tchuente [1986], Computation
on
binary tree network.
Discrete
Appl.
Math.,
14
(1986),
295-310.
M.
Tchuente [1988], Computation
on finite
networks
of
automata.
In
Automata
Networks,
C.
Choffrut, ed., Lecture Notes
in
Comput. Sci. 316,
Springer-Verlag,
New
York,
1988,53-67.
252
Bibliography
T.
Toffoli
[1978],
Integration
of
Phase-Difference Relations
in
Asynchronous Sequential
Networks.
In
Automata, Languages,
and
Programming,
G.
Ausiello
and C.
Bohm,
eds., Lecture Notes
in
Comput.
Sci.
62,
Springer-Verlag,
New
York,
1978,
457-463.
R.
Tucci [19881,
A
note
on the
decomposition
of
infinite automata. Intern.
J.
Computer
Math.,
24
(1988),
141-149.
R.
Tucci [1989],
A
decomposition theory
for a
class
of
infinite transformation semigroups.
Acta Cybernet.,
9
(1989),
39-54.
T.
Toffoli
and N.
Margolus, Cellular Automata Machines,
MIT
Press, Cambridge, Mass.,
1987.
V.
I.
Varshavsky [1968], Collective behaviour
and
control problems. Machine
Intell,
3
(1968),
217-242.
V.
I.
Varshavsky
[1969],
The
organization
of
interaction
in
collectives
of
automata. Machine
Intell,
4(1969),
285-311.
V.
I.
Varshavsky
(ed.)
[1990], Self-timed control
of
concurrent processes.
In The
Design
of
Aperiodic
Logical Circuits
in
Computers
and
Discrete Systems. Math. Appl. (Soviet
Ser.)
52,
Kluwer Academic Publishers, Dordrecht, Netherlands,
1990.
V.
I.
Varshavsky
and B. L.
Osievich [1965], Networks composed
of
ternary majority
ele-
ments.
IEEE
Trans.
Electronic Computers,
14
(1965),
730-733.
H.
Wielandt
[1964],
Permutation
Groups.
Academic Press,
New
York,
1964.
D.
Wood
[1987],
Theory
of
Computation.
John Wiley
and
Sons,
New
York,
1987.
M.
Yoeli
[1961],
The
cascade decomposition
of
sequential machines.
IRE
Trans.
Electronic
Comput.,
10
(1961),
587-592.
M.
Yoeli
[1965],
Generalized cascade decompositions
of
automata.
J.
Assoc. Comput.
Machinery,
12
(1965),
411-422.
V.
P.
Zarovnyi
[1965],
Automaton mappings
and
wreath products
(in
Russian). Kibernet.,
1
(1965),
29-36;
translated
in
Cybernet.,
1
(1965),
29-36.
H. P.
Zeiger
[1967],
Cascade synthesis
of finite-state
machines.
Inform,
and
Control,
10
(1967),
419-433
(plus erratum).
Index
alphabet,
3
antihomomorphism,
4
anti-isomorphism,
5, 27
aperiodic
automaton,
74
semigroup,
74
transformation
semigroup,
74
associative law,
4
asynchronous
automata network,
199
asynchronous automata network
behavior
of,
222,
223
automata network,
44, 58, 60
asynchronous, 199, 220,
221
behavior
of, 223
state-homogeneous,
44,
199, 200,
208
synchronous,
220
underlying digraph
of, 200
automaton
#r,84
k-channel,
183
aperiodic,
74
autonomous,
44
cellular,
199
characteristic semigroup
of, 50, 55
commutative,
45
connected,
44
counter,
45, 156
counter with identity,
45, 224
definite,
45
directable,
45
discrete,
44, 55
elevator,
45
embedding,
46
flip-flop, 46
generalized
cellular,
231
generalized
definite,
45
identity-reset,
44
monotone,
44
nilpotent,
44
one-channel analog
of
k-channel
automaton,
183
prime divisors
of, 74
reset,
44, 83
reverse definite,
45
semi-elevator,
114
set of
generators
of, 44
strongly connected,
44
trivial,
44
weakly
(h,
k)
-definite,
45
weakly k-definite,
45
weakly nilpotent,
44
weakly
reverse
k-definite,
45
automorphism,
4
basis,
4
behavior
of
asynchronous automata network,
222,
223
of
synchronous automata network,
221,
223
branch,
24, 37
catenation,
3
cells
of
cellular automaton,
232
cellular automata,
199
implementations,
233
class
of
automata,
64
commutator,
8
compatibility
253
254
Index
for
a
digraph (elementary),
26
complete
penultimate permutation,
32, 33, 36,
37
completeness
precomplete class,
90
group
complete
(for
classes
of
digraphs),
42
homomorphic representations
with
respect
to
-product,
161
homomorphic representations with
respect
to
general product,
161
penultimate permutation,
29, 32
with
respect
to
homomorphic
representation
for
general
product,
67
with
respect
to
simulation under
projection,
208
component
of
a
mapping,
3
composition
series,
20
configuration
group,
27
semigroup,
27
space,
26
configurations
permutation group
on, 27
transformation
semigroup
on, 27
conjugation,
5
coset
left,
6
right,
6
counter,
45
modulo
n, 45
of
length
n, 45
counter with identity,
45, 224
modulo
n, 45
of
length
n, 45
covering
spatial-temporal,
223
criterion
Krohn-Rhodes,
74
Letichevsky's,
68, 72, 98,
141, 142,
147,
152, 155-157, 159-161,
166,
167, 172, 174, 176, 180,
182,
197
semi-Letichevsky,
68, 121
size,
114
without
Letichevsky
criteria,
68
cycle,
24
disjointness,
24
length
of, in an
automaton,
46
of
length
n, 9
real,
24, 166
dead
state,
44
digraph,
23,
200, 207-211, 213,
214
n-complete,
41
associated undirected graph,
24
centralized,
24, 210
connected
for a
vertex,
24
group n-complete,
41
homomorphically n-complete,
39, 41
homomorphically group n-complete,
40, 41
homomorphism onto,
24
intercommunication,
xi, 25
isomorphically n-complete,
39, 41
isomorphically group n-complete,
40,
41
isomorphism,
24
outerplanar,
25
penultimately permutation complete,
29
planar,
25
strongly connected,
24, 37, 210
with
all
loop edges,
24
direct product
of
transformation semigroups,
15
directed graph,
see
digraph
distance
in
an
undirected graph,
24
division
for
automata,
54
in
equal
lengths,
54
of
automata
by
semigroups,
56
in
equal lengths,
56
of
semigroups,
5, 16
of
transformation semigroups,
16,
17
Index
255
duality
between position
and
contents,
13,
21, 27, 30
edge
endpoints,
24
loop,
24
of
a
digraph,
23
of
undirected graph,
24
self-loop,
24
elementary
collapsing,
9
D
(l)
-compatible,
26
embedding
in
equal lengths,
56, 83
of
semigroups,
16
of
transformation semigroups,
15
face,
25
boundary
of, 25
outer,
25
unbounded,
25
faithful
semigroup action,
15
feedback,
60, 62
function,
59
feedback
function
for
asynchronous automata network,
220
function,
2
bijective,
2
composite,
2
extension
of, 2
image
of, 2
injective,
2
one-to-one,
2
onto,
2
rank
of, 2
restriction
of, 2
surjective,
2
generating system,
4
minimal,
4
graph,
24
complete,
25
complete bipartite,
25
outerplanar,
25,
163,
166
planar,
24
subdivision
of, 25
underlying,
62
group,
5
alternating,
9, 43
cyclic,
7
factor
group
of, 7
irreducible,
75
noncommutative,
98
prime,
75
simple,
7, 73, 75, 81
trivial,
5
holonomy,
77
homomorphic image
of
semigroup,
4
homomorphic
representation,
46, 55
completeness
for
with respect
given
product,
66
homomorphic simulation,
53, 55
completeness
for
with respect
given product,
66
homomorphism
of
automata,
46
of
monoids,
5
of
semigroups,
4
idempotent,
5
identity
element,
5
index
to
next
available
letter,
223
inverse element,
5
isomorphic representation,
46, 63
completeness
for
with
respect
given
product,
66
isomorphic
simulation,
53
completeness
for
with respect
given
product,
66
isomorphism
of
automata,
46
of
semigroups,
4
Jordan-Holder
factor,
20
,63
to
a
to
a
to a
to
a
256
Index
left
identity element,
5
left
zero,
5
lemma
position-contents duality (Corollary
1.7),
13
length
of
a
path,
24
local
finiteness
of
digraph,
220
local time, 225, 227,
229
map
induced
configuration
map,
26
minimal
element
of
partially ordered set,
3
monoid,
5
characteristic monoid
of an
automa-
ton,
50, 51, 53, 55
flip-flop,
5,
73, 75, 81
free,
3
trivial,
5
neighbor
of
a
node
in
digraph,
219
neighborhood
of
a
node
in
digraph,
219
network
D-, 200
topology,
199
networks
genetic regulatory,
23
neural,
23
of
automata,
23
next available letter
which
may be
read
at a
node
in an
asynchronous automata network,
223
nodes
of
a
digraph,
23
normalize,
6
order
of
a
digraph,
24
of
a
group element,
7
ordered cycle property
and
primitive products, 165,
166
for
digraphs,
25
for
graphs,
24
ordering
cyclic,
41
partition,
2
path
directed,
24
permutation,
2, 9
cyclic,
9
complete,
9
of
a
word,
4
even,
9
holonomic,
77
inversion
in a, 9
on
configurations
of a
digraph,
27
permutation group,
9, 76
full,
10
holonomy,
77
position-contents duality
and
time reversal,
13, 21
position-contents
duality,
13
power
cartesian,
3
of
a
word,
3
of
semigroup element,
5
product
D-, 63
-,62
-,
60, 62
-,
66
, 161
-V2-,
164
-, 60
q-,62
cartesian,
2
cascade,
60, 62, 66, 84
diagonal,
47
direct,
47
direct
for
semigroups,
7
feedback-free,
60
general,
58, 67, 161
generalized,
59
Gluskov,
58, 72, 73,
157, 160, 162,
182
loop-free,
62
Index
257
parallel,
62
primitive,
163-165
quasi-direct,
62
right, 2
single
factor,
156
single-factor,
159
temporal, 184,
192
with
feedback,
60
wreath,
14, 78
projection
H-, 3
completeness under,
for
networks,
200
read
functions
of
asynchronous automata network,
221
really independent,
3
relation,
2
antysimmetric,
2
congruence,
6
equivalence,
2
linear ordering,
2
partial ordering,
2
pre-order,
2
reflexive,
2
symmetric,
2
total
ordering,
2
transitive,
2
right
identity element,
5
right
zero,
5
semigroup,
4
abelian,
4
aperiodic,
74
characteristic semigroup
of an au-
tomaton,
50, 53, 55, 56, 58, 73
commutative,
4
finitely
generated,
4
generated
by a
subset,
4
irreducible,
75, 81
of
all
subsets
of
semigroup,
4
quotient,
6
set
ordered,
3
partially ordered,
3
source
of
a
mapping,
2
of
an
edge,
24
spatial-temporal covering,
229
spatial-temporal
section,
231
natural,
231
subautomaton,
46
input,
46
state,
46
subgroup,
6
commutator,
8
derived,
8
generated
by a
subset,
6
generated
by an
element,
6
normal,
6
proper normal,
7
submonoid,
6
subnormal chain,
20
subsemigroup,
4, 6
of
the flip-flop
monoid,
81
subword,
3
symmetric semigroup,
8
synchronous automata network
behavior
of, 223
target
of
a
mapping,
2
of
an
edge,
24
theorem
Esik-Horvath
characterization theo-
rem
(Theorem 5.27), 145,
162
asynchronous emulation
of
cellular
automata
(Theorem
7.30),
233
asynchronous emulation
of
synch-
ronous automata networks
(Theorem 7.22),
224
asynchronous emulation
of
synch-
ronous generalized cellular
automata
(Theorem 7.29),
232
Chartrand-Harary outerplanarity
(Theorem 2.2),
25
Denes-Hermann
(Theorem 1.3),
8
GluSkov
decomposition (Theorem
2.68),
23, 67
258
Index
holonomy decomposition (Theorem
3.9),
74, 77, 78, 82
Jordan-Holder
coordinate theorem
for
finite
groups (Theorem
1.19),
21
Jordan-Holder
theorem
for finite
groups
(Theorem
1.18),
20
Krohn-Rhodes
decomposition
(Theorem 3.1),
73, 82
Krohn-Rhodes
prime decomposition
(Theorem 3.2),
74, 77, 82
Kuratowski
planar graph (Theorem
2.1),
25
Lagrange coordinate decomposition
(Theorem 1.17),
20, 21
Lagrange coordinates (Lemma 1.16),
19
Letichevsky decomposition (Theo-
rem
2.69),
23, 67, 68, 162
tile,
77, 78
transformation
allowed,
29
compatible (elementary),
26
transformation
group,
9
transformation
semigroup,
8
aperiodic,
74
flip-flop,
14,
76
full,
10
height
of, 78
identity-reset,
76
of
a
digraph,
39
on
configurations
of a
digraph,
27
permutation-reset,
76
prime
divisors
of, 74
wreath
product,
14
transformations
interpretation
1 of, 10, 26
interpretation
2 of, 12
multiplication
of, 8
on
a
set,
8
transposition,
9
Turing
machine,
233
universal
computation
asynchronous,
233
update
asynchronous
local,
221
local
+1-update,
226
real update
at a
vertex,
226
set of
nodes,
221
update
pattern, 221,
234
vertex
free,
28
of
a
digraph,
23
walk
closed,
24
word,
3
control,
152
empty,
3
length
of, 3
mirror image
of, 3
prefix
of, 3
reverse
of, 3
suffix
of, 3
zero element,
5