## An Introduction to Sequential Dynamical SystemsSequential 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

### Contents

1 | |

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 |

237 | |

245 | |