Sequential Dynamical System¶

A finite graph dynamical system whose one-step evolution is the ordered composition of neighborhood-local vertex updates, so later updates in the schedule read changes made earlier in the same sweep.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2758
Origin domain: discrete dynamical systems
Subdomain: asynchronous graph dynamics

Core Idea¶

A sequential dynamical system (SDS) is a finite graph dynamical system whose global evolution rule is built by applying vertex-local update maps one at a time in a specified order. Each vertex carries a state. Its local rule reads the current states in a graph-defined neighborhood and writes a new state only at that vertex. Because an update is committed immediately, a vertex appearing later in the schedule can read values written earlier in the same sweep. The schedule is therefore part of the mathematical model: changing it can change the global map, its transient trajectories, and its periodic behavior even when the graph and local functions stay fixed.^[1]^[2]

Let $Y=(V,E)$ be a finite graph with $V=\{1,\ldots,n\}$, and for simplicity let each vertex state lie in a finite set $K$. A global configuration is

\[ x=(x_1,\ldots,x_n)\in K^n. \]

For each vertex $i$, a local rule $f_i$ reads the state on $i$ and its prescribed neighborhood. Its lifted local map $F_i:K^n\to K^n$ changes only coordinate $i$:

\[ F_i(x)_j= \begin{cases} f_i(x[i]), & j=i,\\ x_j, & j\ne i, \end{cases} \]

where $x[i]$ is the ordered tuple of states visible to $i$. For an update word $w=(w_1,\ldots,w_m)$, the global SDS map is

\[ [F_Y,w] = F_{w_m}\circ F_{w_{m-1}}\circ\cdots\circ F_{w_1}. \]

Thus $F_{w_1}$ acts first. Iterating this one-sweep map produces the discrete-time dynamics. Early formulations often take $w$ to be a permutation, so every vertex is updated exactly once per sweep. Later work also treats words that can repeat vertices; some conventions require a fair word in which every vertex appears at least once.^[3]^[4]

The candidate survives as an autonomous domain-specific abstraction. prime:network, prime:sequencing, prime:iteration, prime:temporal_dynamics, and prime:fixed_point cover important ingredients and consequences. Their conjunction still does not specify graph-local maps, immediate write-back, ordered functional composition, the distinction between permutation and word schedules, or the induced finite phase space. SDS is a mature formalism with its own equivalence, reachability, schedule-stability, and phase-space questions.

Structural Signature¶

An SDS has these mandatory roles:

A finite dependency graph $Y$. Its vertices are the updating entities, and its edges or directed neighborhoods state which vertex values a local rule may inspect. The graph is interaction support, not the phase space.
Vertex state sets. A common finite alphabet $K$ is standard, especially $K=\{0,1\}$ or a finite field, though heterogeneous finite state sets are possible in broader formulations.
A global configuration. The product state $x\in K^n$ records all vertex states at a sweep boundary.
A local rule for every vertex. $f_i$ computes the proposed state of vertex $i$ from the current configuration restricted to its allowed neighborhood.
A lifted local map. $F_i$ writes the result at coordinate $i$ and leaves every other coordinate unchanged. This lift makes the local rules composable as self-maps of the common global state space.
An update word or permutation. $w$ names the order in which the lifted maps act. A permutation SDS updates every vertex once; an SDS over words can repeat vertices and may impose fairness.
Immediate state visibility. The output of $F_{w_k}$ becomes the input to $F_{w_{k+1}}$. This is the constitutive difference from parallel update.
A global sweep map. Ordered composition produces one deterministic map $[F_Y,w]:K^n\to K^n$.
Iteration and phase space. Repeating the same global map creates trajectories $x,F(x),F^2(x),\ldots$. Its phase space is the directed graph with one vertex for each configuration and one outgoing edge $x\to F(x)$.
A constituent-to-dynamics question. Analysis asks how graph structure, local rules, and schedule constrain fixed points, periodic orbits, basins, predecessors, reachability, equivalence, or sensitivity.

The recognition test is exact: identify the dependency graph, state alphabet, neighborhood-local functions, lifted one-coordinate maps, fixed update schedule, ordered composition, and induced phase-space map. A system that merely runs code sequentially, or one whose “nodes” do not have graph-local state updates, does not qualify.

What It Is Not¶

Not a generic discrete dynamical system. Every SDS induces a self-map on a finite state space, but a generic finite map need not factor into graph-local one-coordinate updates under a declared schedule.
Not a synchronous graph dynamical system. Synchronous update evaluates all local rules against the same pre-step configuration and commits them together. An SDS commits after each vertex, so later rules see earlier writes.
Not every asynchronous system. Random asynchronous cellular automata, event-driven systems, block-sequential systems, and systems with time-varying schedules can be modeled by related graph-dynamics formalisms. A deterministic SDS fixes a word or permutation for constructing its global map unless an extension explicitly adds schedule variation.
Not classical cellular automata as such. A classical cellular automaton ordinarily uses a regular lattice, a spatially homogeneous local rule, and simultaneous update. Sequential cellular automata arise as a specialization when the graph and local functions preserve the cellular structure but updates occur in sequence.^[3]
Not a Boolean network merely because $K=\{0,1\}$. Boolean networks can use synchronous, asynchronous, stochastic, or other update semantics. The local Boolean functions and update schedule must jointly satisfy the SDS construction.
Not a dynamic Bayesian network. An SDS is a deterministic finite-state update formalism in its recognition center. A dynamic Bayesian network specifies probabilistic conditional distributions over time slices.
Not an agent-based model in general. Many simulations have agents and schedules, but SDS requires an explicit finite graph, neighborhood-local vertex state, and a global map built by ordered local composition.
Not the update schedule alone. The same word can govern many different SDSs. Graph, local functions, state space, and schedule are all identity-bearing.

Scope of Application¶

SDS belongs to discrete mathematics, finite dynamical systems, graph dynamics, theoretical computer science, and simulation theory. It was developed as a mathematical framework for systems whose global behavior emerges from local, interacting updates implemented in a sequence. The formalism supports both structural questions—when do different orders induce the same map or cycle structure?—and computational questions—does a configuration have a predecessor, can a target be reached, or does some update permutation realize a requested transition?^[5]^[6]

Studied families include Boolean SDSs, linear SDSs over finite fields, threshold and symmetric-function systems, sequential cellular automata, and graph-constrained models motivated by networks and computer simulations. Linear systems expose matrix and incidence-algebra structure; asynchronous cellular automata expose how a regular local rule changes when parallel update is replaced by an order; computational-complexity work separates tractable and intractable predecessor or schedule-existence problems.^[7]^[5]

The framework can inform models of distributed interaction, regulatory or influence networks, communicating state machines, and agent simulations when their details actually instantiate the graph-local finite-state schedule. An application label alone is insufficient. A biological network with continuous stochastic kinetics or an epidemic simulator with mobile agents and nonlocal event queues may require a richer model even if it has sequential execution.

The standard deterministic SDS freezes $Y$, the local maps, and $w$ while the global map is iterated. Stochastic graph dynamical systems, schedules sampled anew on each step, block updates, evolving graphs, infinite state sets, and continuous time are extensions or neighboring formalisms. They should be described with their extra semantics rather than silently absorbed into the core node.

Clarity¶

The fastest diagnostic is to compare two formulas. In a synchronous system,

\[ F_{\mathrm{sync}}(x)=\bigl(f_1(x[1]),\ldots,f_n(x[n])\bigr), \]

so every component reads the same old $x$. In an SDS,

\[ F_{\mathrm{seq}}(x)=F_{w_m}(\cdots F_{w_2}(F_{w_1}(x))\cdots), \]

so each read may occur after some coordinates have changed. If all local updates commute, some or all reorderings can be functionally equivalent. If they do not, order is causally active.

A second diagnostic separates the dependency graph from the phase-space graph. $Y$ has $n$ vertices and tells each local rule what it may read. The phase space has up to $|K|^n$ vertices, one for every global configuration, and records the action of the completed global map. Confusing the two erases the central research problem: infer the large phase-space dynamics from the much smaller constituent graph, rules, and schedule.

A third diagnostic asks what “one time step” means. In the SDS convention used here, a macro-step is one complete traversal of the update word. Intermediate local updates are microsteps inside it. Comparing an intermediate state to a synchronous one-step result without aligning those clocks produces a false discrepancy.

Manages Complexity¶

An arbitrary map on $K^n$ can require a table with $|K|^n$ entries. SDS factorizes the map into $m$ local operations, each constrained by a graph neighborhood. This exposes a compact generative description: network structure says who can influence whom, local functions say how influence changes one vertex, and the update word says when that change becomes visible.

The factorization creates analytic leverage. Local maps attached to vertices with no dependency relation can commute, so adjacent independent updates may be swapped without changing the global function. Permutation schedules can be grouped by functional or cycle equivalence rather than evaluated one by one. Graph invariants, acyclic orientations, and algebraic relations can then bound how many genuinely different global behaviors the schedules can generate.^[6]

The same factorization also exposes where complexity enters. A small change in update order may alter transients or cycles when neighboring local maps do not commute. A phase space grows exponentially with vertex count even when each rule is simple. Reachability and predecessor questions can therefore be difficult despite a compact model description. SDS does not make all network dynamics easy; it makes the sources of difficulty explicit and mathematically addressable.

Abstract Reasoning¶

Several deductions follow directly from the composition structure.

First, schedule sensitivity is a noncommutativity question. If two consecutive local maps satisfy $F_iF_j=F_jF_i$, swapping them leaves the global map unchanged. For standard neighborhood-local rules on an undirected graph, updates at nonadjacent vertices do not read one another's coordinates and therefore commute. Schedule differences generated solely by such swaps are functionally neutral. Edges mark where order dependence may enter, though special functions on adjacent vertices can commute as well.^[1]

Second, every deterministic finite SDS phase space is a functional digraph: each configuration has exactly one outgoing edge. Consequently, every trajectory eventually reaches a directed cycle, with transient in-trees feeding the periodic states. A fixed point is a one-cycle. This conclusion uses finiteness and determinism, not any special Boolean rule.

Third, functional equivalence and cycle equivalence are different. Two schedules can induce different global maps yet have isomorphic periodic-orbit subgraphs. Cyclic shifts of an update word preserve cycle structure under broad finite conditions, even though transient structure or pointwise transitions may differ.^[6] An analyst must therefore name whether “same dynamics” means identical map, conjugate full phase space, identical periodic points, or isomorphic cycle structure.

Fourth, fixing the local rules does not eliminate a modeling choice. Selecting $w$ can be an intervention that changes reachability, basins, or cycle structure. Conversely, proving update-order independence shows that a class of conclusions is robust to that choice. The schedule is both a semantic component and a sensitivity axis.

Knowledge Transfer¶

SDS carries a useful modeling pattern across finite networked domains:

\[ \text{interaction graph} + \text{local state rules} + \text{visibility schedule} \longrightarrow \text{global map and phase space}. \]

The transfer is literal when a target system supplies all four parts. A Boolean regulatory model can use genes or logical variables as vertices, local regulatory logic as $f_i$, and an explicit sequential schedule as $w$. A communicating-state model can use process states at vertices and neighbor messages in the local rules if the finite-state and fixed-schedule assumptions are maintained. A sequential cellular automaton uses a regular graph and typically a shared local rule, making it a constrained SDS family.

The transferable lesson is not simply “order matters.” It is that write visibility plus noncommuting local maps is the mechanism by which order matters. This directs analysis toward the dependency graph and commutation relations rather than toward arbitrary enumeration of schedules.

Transfer stops when updates are continuous, globally coupled, probabilistic without an expanded state construction, or scheduled by endogenous events not captured in a fixed word. Such systems may still instantiate Network, Sequencing, Temporal Dynamics, or Iteration, but they are not automatically Sequential Dynamical Systems.

Examples¶

NOR system on a triangle. Let $Y$ be the three-vertex complete graph, $K=\{0,1\}$, and let every vertex use the Boolean NOR of its closed neighborhood. With update order $w=(1,2,3)$, start at $000$. Vertex 1 reads \$000$ and becomes 1, giving $100$. Vertex 2 now reads the *updated* \$100$ and remains 0; vertex 3 does the same. Thus the sweep map sends

\[ 000\mapsto100. \]

Repeating the same ordered sweep gives

\[ 100\mapsto010\mapsto001\mapsto000, \]

a four-cycle. Reversing the schedule sends $000$ first to $001$ instead, showing that the schedule changes the pointwise global map even though the same four states can remain in the periodic structure. This example maps every role: the triangle is $Y$, binary values form $K$, NOR supplies each $f_i$, the order supplies $w$, immediate writes distinguish the map, and iteration exposes the cycle.^[6]

Two-vertex noncommutation. On an edge with binary state, let vertex 1 copy vertex 2, $f_1(x_1,x_2)=x_2$, and let vertex 2 write the complement of vertex 1, $f_2(x_1,x_2)=1-x_1$. From $00$, order $(1,2)$ gives $00\to00\to01$, whereas order $(2,1)$ gives $00\to01\to11$. The local rules and graph are identical; only composition order differs. The example isolates noncommutativity without relying on a large phase space.

Linear SDS. If $K$ is a finite field and every $F_i$ is linear, the global map is a product of sparse local-update matrices in schedule order. Changing order changes the matrix product unless the relevant factors commute. Linear SDSs are a mature subclass with explicit formulas and connections to incidence algebras and Möbius functions.^[7]

Predecessor question. Given a target configuration $y$, one can ask whether some $x$ satisfies $[F_Y,w](x)=y$. Such a state is a predecessor; a state with none is a Garden-of-Eden configuration. Complexity depends sharply on the state domain, functions, and graph restrictions. This is a property of the SDS map and should not be inferred merely from visual inspection of the dependency graph.^[5]

Structural Tensions¶

Local simplicity versus global complexity. Each update may read only a small neighborhood and change one coordinate, while the phase space has exponentially many configurations and can contain long transients or many cycles.
Schedule as model semantics versus schedule as implementation artifact. When local maps do not commute, order changes the mathematical system. Treating a programming loop order as incidental can therefore change the model being simulated.
Expressiveness versus identifiability. Graph, rules, and schedule can encode diverse dynamics, but observing a global trajectory need not uniquely identify which constituent triple generated it.
Functional equivalence versus cycle equivalence. Schedules can disagree on transient transitions while agreeing on periodic-orbit structure. A claim of “same behavior” must specify the equivalence relation.
Fixed-order analyzability versus asynchronous realism. A fixed schedule yields one deterministic map and clean phase-space theory. Real systems may use variable, random, or endogenous timing, requiring a stochastic or nondeterministic extension.
Word generality versus permutation clarity. Allowing repeated vertex labels models unequal update frequencies, while permutation schedules keep one sweep comparable across vertices. Results proved for one convention do not automatically transfer to the other.
Graph locality versus hidden global dependence. A compact graph is meaningful only if local functions truly use the declared neighborhoods. Smuggling global variables into $f_i$ makes the support graph misleading.

Structural–Framed Character¶

Sequential Dynamical System is strongly structural. Once the graph, state sets, local functions, and update word are specified, ordered composition fixes the global map exactly. Immediate write visibility, phase-space construction, schedule commutation, and functional equivalence are mathematical commitments rather than interpretive framing.

The domain frame determines which entities become vertices, which dependencies become edges, which states and rules are meaningful, and whether a fixed sweep approximates the target process. Those choices govern model validity but do not alter the formal SDS identity. The abstraction is therefore a formal domain-specific construction: more structural than framed, but not a prime because its recognition depends on graph-dynamics objects and finite-state update semantics.

Structural Core vs. Domain Accent¶

The structural core is

\[ \text{product state} \rightarrow \text{local single-coordinate maps} \rightarrow \text{ordered composition with immediate visibility} \rightarrow \text{iterated global map}. \]

The domain accent is the discrete graph-dynamics grammar: vertices, neighborhoods, finite alphabets, update words, sweep maps, phase spaces, periodic orbits, and schedule equivalence. Generalizing away those objects leaves Network, Sequencing, Composition, and Iteration but loses the named formalism. The residual is not prime because “do local things in order” alone does not say what counts as local, which state is visible, or how a phase-space transition is formed.

Network is the most literal parent. An SDS is a network together with a declared state process: vertices carry values, edges constrain interactions, and structural properties are used to reason about the global dynamics. The proposed DAG edge therefore treats Sequential Dynamical System as a strict domain-specific subtype of prime:network.

Sequencing explains why arrangement of the same local updates can determine the outcome. Iteration explains repeated application of the completed sweep map. Temporal Dynamics covers sensitivity to order and timing. Fixed Point and Recurrence name phase-space outcomes, not the whole SDS. Composition explains construction of the global map from local maps. None individually, or as an unstructured bundle, supplies the graph-local immediate-write formalism.

Relationships to Other Abstractions¶

Current abstraction Sequential Dynamical System Domain-specific

Parents (1) — more general patterns this builds on

Sequential Dynamical System is a kind of Network Prime

Network is the most literal parent.

Hierarchy path (1) — routes to 1 parentless root

Sequential Dynamical System → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Sequential Dynamical System sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

prime:network. Network supplies nodes, edges, and possibly dynamics. SDS adds finite vertex state, local one-coordinate maps, a fixed sequential schedule, immediate visibility, and a global phase-space map.
prime:sequencing. The update word is a sequence, but the SDS is the graph, rules, state space, and induced dynamics together.
prime:iteration. Iteration repeats the sweep map; it does not define how the sweep map is factorized.
prime:fixed_point or prime:recurrence. These classify behaviors in an SDS phase space. An SDS may have several cycles and no fixed point, so neither is an alias.
Synchronous dynamical system. Parallel updates read one common prior state. Sequential updates read and write through an ordered chain of intermediate states.
Asynchronous cellular automaton. It is a closely related or specialized family when the support graph and local rules have cellular-automaton structure. Broader asynchronous scheduling may exceed a fixed-word SDS.
Finite dynamical system or graph dynamical system. These are superclasses. SDS is distinguished by sequential composition of local maps.
Dynamic Bayesian network. It is probabilistic and time-sliced rather than a deterministic ordered composition of vertex maps.
Sequential logic or sequential program execution. Shared vocabulary does not supply the SDS graph/state/map identity.

References¶

[1] Henning S. Mortveit and Christian M. Reidys, An Introduction to Sequential Dynamical Systems (Springer, 2008). Publisher record and DOI. registry ↩a ↩b

[2] Henning S. Mortveit and Christian M. Reidys, “Discrete, Sequential Dynamical Systems,” Discrete Mathematics 226 (2001): 281–295. DOI. registry ↩

[3] Matthew Macauley, Jon McCammond, and Henning S. Mortveit, “Dynamics Groups of Asynchronous Cellular Automata,” Journal of Algebraic Combinatorics 33 (2011): 11–35. DOI; author-hosted manuscript. registry ↩a ↩b

[4] Christian M. Reidys, “Sequential Dynamical Systems over Words,” Annals of Combinatorics 10 (2006): 481–498. DOI. registry ↩

[5] Chris Barrett, Harry B. Hunt III, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns, “Predecessor and Permutation Existence Problems for Sequential Dynamical Systems,” Discrete Mathematics and Theoretical Computer Science, AA(DMCS) (2003): 69–80. Journal PDF. registry ↩a ↩b ↩c

[6] Matthew Macauley and Henning S. Mortveit, “Cycle Equivalence of Graph Dynamical Systems,” Nonlinearity 22 (2009): 421–436. DOI; author preprint. registry ↩a ↩b ↩c ↩d

[7] Ricky X. F. Chen and Christian M. Reidys, “Linear Sequential Dynamical Systems, Incidence Algebras, and Möbius Functions,” Linear Algebra and its Applications 553 (2018): 270–291. DOI; author preprint. registry ↩a ↩b