An Introduction to Sequential Dynamical Systems

Springer Science & Business Media, Nov 27, 2007 - Mathematics - 248 pages

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