An Introduction to Sequential Dynamical Systems

Front Cover
Springer Science & Business Media, Nov 27, 2007 - Mathematics - 248 pages
0 Reviews

Sequential Dynamical Systems (SDS) are a class of discrete dynamical systems which significantly generalize many aspects of systems such as cellular automata, and provide a framework for studying dynamical processes over graphs.

This text is the first to provide a comprehensive introduction to SDS. Driven by numerous examples and thought-provoking problems, the presentation offers good foundational material on finite discrete dynamical systems which leads systematically to an introduction of SDS. Techniques from combinatorics, algebra and graph theory are used to study a broad range of topics, including reversibility, the structure of fixed points and periodic orbits, equivalence, morphisms and reduction. Unlike other books that concentrate on determining the structure of various networks, this book investigates the dynamics over these networks by focusing on how the underlying graph structure influences the properties of the associated dynamical system.

This book is aimed at graduate students and researchers in discrete mathematics, dynamical systems theory, theoretical computer science, and systems engineering who are interested in analysis and modeling of network dynamics as well as their computer simulations. Prerequisites include knowledge of calculus and basic discrete mathematics. Some computer experience and familiarity with elementary differential equations and dynamical systems are helpful but not necessary.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

What is a Sequential Dynamical System?
1
12 Motivation
4
13 Application Paradigms
7
132 Task Scheduling and Transport Computations
13
Characteristics and Research Questions
16
142 PhaseSpace Structure
17
15 Computational and Algorithmic Aspects
18
16 Summary
20
PhaseSpace Structure of SDS and Special Systems
129
52 FixedPoint Computations for General Graphs
137
53 Threshold SDS
139
54 SDS over Special Graph Classes
140
541 SDS over the Complete Graph
141
542 SDS over the Circle Graph
143
543 SDS over the Line Graph
145
544 SDS over the Star Graph
146

Answers to Problems
22
A Comparative Study
23
212 Structure of Cellular Automata
24
213 Elementary CA Rules
27
22 Random Boolean Networks
33
23 FiniteState Machines FSMs
34
Problems
35
Answers to Problems
37
Graphs Groups and Dynamical Systems
38
311 Simple Graphs and Combinatorial Graphs
41
312 The Adjacency Matrix of a Graph
44
313 Acyclic Orientations
46
314 The Update Graph
47
315 Graphs Permutations and Acyclic Orientations
48
32 Group Actions
50
321 Groups Acting on Graphs
51
322 Groups Acting on Acyclic Orientations
52
33 Dynamical Systems
56
331 Classical Continuous Dynamical Systems
57
332 Classical Discrete Dynamical Systems
59
333 Linear and Nonlinear Systems
61
Problems
63
Answers to Problems
66
Sequential Dynamical Systems over Permutations
69
412 Sequential Dynamical Systems
71
413 The Phase Space of an SDS
73
414 SDS Analysis A Note on Approach and Comments
76
In this section we present some elementary properties of SDS 421 Decomposition of SDS
77
422 Fixed Points
78
423 Reversible Dynamics and Invertibility
80
424 Invertible SDS with Symmetric Functions over Finite Fields
84
43 Equivalence
88
431 Functional Equivalence of SDS
90
432 Computing Equivalence Classes
91
433 Dynamical Equivalence
93
434 Enumeration of Dynamically Nonequivalent SDS
97
44 SDS Morphisms and Reductions
103
441 Covering Maps
104
443 Reduction of SDS
105
444 Dynamical Equivalence Revisited
109
445 Construction of Covering Maps
110
446 Covering Maps over Qnα
111
447 Covering Maps over Cir
119
Problems
121
Answers to Problems
122
551 SDS Induced by norkk and nandkk
147
552 SDS Induced by nork + nandkk
154
Problems
158
Answers to Problems
160
Graphs Groups and SDS
164
611 Preliminaries
166
612 The Group GYFY
167
613 The Class of wIndependent SDS
171
62 The Class of wIndependent SDS over Circn
174
621 The Groups GCirc₄ Fcirc₄
176
63 A Presentation of S₃₅
178
Problems
179
Answers to Problems
182
Combinatorics of Sequential Dynamical Systems over Words
185
71 Combinatorics of SDS over Words
187
712 Automorphisms
189
713 Words
192
714 Acyclic Orientations
193
715 The Mapping Oy
195
716 A Normal Form Result
197
717 The Bijection
198
72 Combinatorics of SDS over Words II
199
722 The Bijection P1
201
723 Equivalence P2
204
724 PhaseSpace Relations
206
Problems
209
Answers to Problems
210
Outlook
213
811 Random Update Order
214
812 SDS over Random Graphs
217
822 The TryptophanOperon
218
83 Evolutionary Optimization of SDSSchedules
220
832 Distances
223
833 A ReplicationDeletion Scheme
226
834 Evolution of SDSSchedules
227
835 PseudoCodes
228
84 Discrete Derivatives
229
85 RealValued and Continuous SDS
231
86 LLocal SDS
233
87 Routing
234
872 Protocols as Local Maps
235
References
237
Index
245
Copyright

Common terms and phrases