1 State graph basics

1.1 Definition and intuition

A state graph is a mathematical model in which a system’s possible configurations are represented as *states*, and the allowable changes between these configurations are represented as *transitions*. By organizing states and transitions into a graph, one can study how the system may evolve, which configurations can be reached, and how long certain behaviors can persist.

In many settings, the “system” is abstract: it might be the internal status of a program, the modes of a controller, or the stages of a process. Even when the underlying system is not explicitly drawn, the state graph offers a structured way to reason about its evolution under rules.

1.2 Components: vertices, edges, and transitions

The core building blocks are:

  • Vertices (nodes): represent distinct system configurations.
  • Edges (arcs): represent possible transitions from one configuration to another.
  • Transitions: correspond to specific rule applications or events that move the system from a source state to a target state.

An edge from vertex \(u\) to vertex \(v\) is interpreted as: “if the system is in state \(u\), then the rules allow it to move to state \(v\).”

1.3 Graph directionality and labeling

State graphs are commonly directed: transitions have a source and a destination. Direction matters because a move that is allowed from \(u\) to \(v\) may not be allowed in reverse.

Edges may also carry labels, indicating which event, input, or operation produces the transition. When labels are present, the same pair of states can sometimes be connected by multiple edges, each corresponding to a different triggering condition.

1.4 Common terminology (state, transition, run)

Standard terms used in discussions include:

  • State: a vertex, i.e., a configuration of the system.
  • Transition: an edge, possibly together with its label or triggering condition.
  • Run: an unfolding of the system over time, typically expressed as a sequence of states connected by transitions.
  • Step: one transition in the run, often aligned with one input or one event occurrence.

This terminology supports a shift from static structure (the graph) to dynamic behavior (runs through the graph).

2 Formal modeling

2.1 State graph as a directed graph

A state graph is frequently formalized as a directed graph equipped with a representation for how transitions relate to system evolution.

2.1.1 Vertex sets and state notation

Let \(S\) be a set of states, and let \(s \in S\) denote a generic state. The state graph is then built around \(S\) as the vertex set.

Often, specific states play special roles:

  • An initial state \(s_0\), from which runs begin.
  • Possibly one or more terminal (or accepting, depending on context) states, where certain behaviors end or satisfy a condition.

State graphs can be defined with explicit vertex sets (enumerated states) or implicitly (states described by variable valuations or configuration rules), but in the formal definition they still function as elements of a set.

2.1.1.1 Initial and terminal state conventions

Initial conventions vary by application. In many modeling frameworks, there is a distinguished start state \(s_0\). In other cases, there may be a set of permissible starting states.

Terminal conventions can also vary. A terminal state might mean “no outgoing transitions,” or it might mean “a designated stopping condition is reached even if further transitions exist.” The distinction affects how runs are interpreted when analyzing termination.

2.1.2 Transition relation representation

The allowed moves can be modeled as a transition relation \(R \subseteq S \times S\). Under this view, an ordered pair \((s, t) \in R\) indicates that the system can transition from state \(s\) to state \(t\).

If transitions are labeled by events or inputs, the formal object is often extended with an additional component, such as a set of labels and a relation between states under each label. Conceptually, though, the underlying structure remains “edges encode permissible moves.”

2.2 Deterministic vs nondeterministic transition rules

The difference between deterministic and nondeterministic transition rules concerns whether the next state is uniquely determined by the current state and the triggering condition.

2.2.1 Determinism in outgoing transitions

A transition system is typically deterministic when, for each state (and for each relevant input/event), there is at most one outgoing transition that can occur. In a graph without labels, determinism can be interpreted as: from any state there is at most one outgoing edge, though many practical systems allow multiple outgoing edges based on external conditions.

Determinism is useful for prediction and algorithmic analysis because it reduces branching in runs: once the current state and input are fixed, the next state is fixed.

2.2.2 Nondeterminism and branching behavior

A transition system is nondeterministic when a state may have multiple possible next states under the same triggering condition (or, in an unlabeled setting, multiple outgoing edges). Nondeterminism can represent:

  • choice made by the environment,
  • uncertainty,
  • multiple strategies, or
  • abstraction where finer detail is not modeled.

In a state graph, nondeterminism is expressed directly as branching: a run may follow one of several edges, leading to different future possibilities.

3 Paths and runs

3.1 Paths as sequences of transitions

A path in a directed graph is a sequence of vertices such that consecutive vertices are connected by directed edges. In the state graph setting, a path corresponds to a sequence of transitions that can occur, assuming the system follows those edges.

Paths may be finite or infinite. Finite paths are useful for checking reachability within limited steps, while infinite paths are useful for reasoning about ongoing behavior and recurrent patterns.

3.2 Runs over time or input steps

A run is a path interpreted as an evolution of the system over time. If inputs or events are explicit, a run may be aligned with a sequence of input symbols, where each step selects a transition compatible with the current state and that input.

Runs provide the bridge between the graph’s structure and dynamic execution semantics. Two different runs can share edges in common yet differ in which edges are chosen when nondeterminism exists.

3.3 Reachability

Reachability asks which states can be attained from a given starting point by following directed edges.

3.3.1 Reachable states from an initial state

Given an initial state \(s_0\), a state \(t\) is reachable if there exists a directed path from \(s_0\) to \(t\). This is central for verifying whether certain conditions are ever possible, such as whether a system can enter a particular mode.

In many applications, reachability is computed without enumerating all runs; instead, graph traversal methods explore reachable vertices efficiently.

3.3.2 Induced subgraphs of reachable states

The set of reachable states can be used to form an induced subgraph: it includes only vertices reachable from the initial state and includes those edges whose endpoints both lie in this set. Analyzing this reduced graph often simplifies further reasoning because it removes unreachable structure that cannot affect runs starting from \(s_0\).

3.4 Absorbing states and termination

An absorbing state is one that, once entered, cannot be left—formally, it has transitions only to itself (or the system’s semantics prevent leaving). Absorbing states represent “enduring” conditions, such as a halted mode or a failure state in simplified models.

Termination depends on modeling conventions. In some graphs, termination is captured by reaching a state with no outgoing edges. In others, termination may be tied to a special kind of terminal designation even when outgoing edges exist.

4 Graph properties of interest

4.1 Cycles and recurrence

A cycle occurs when a path returns to a previously visited vertex. Cycles indicate the potential for repeated behavior rather than one-way progression.

4.1.1 Self-loops and their meaning

A self-loop is an edge from a vertex to itself. It often models a “no change” step, such as stuttering, waiting, or receiving an input that leaves the system in the same mode. In analyses, self-loops can affect properties like termination (a system might never exit a self-loop state).

4.2 Strong connectivity and component structure

Directed graphs naturally decompose into regions with mutual reachability.

4.2.1 Strongly connected components (SCCs)

A directed graph is strongly connected if every vertex can reach every other vertex via directed paths. More generally, strongly connected components (SCCs) partition the vertex set into maximal subgraphs where each vertex reaches every other within the subgraph.

SCC structure is valuable because it identifies “feedback” regions: inside an SCC, the system can potentially circulate, while moving between SCCs behaves more like a one-way flow when considering the SCC condensation graph.

4.3 Acyclic state graphs (DAGs)

A state graph with no directed cycles is acyclic. When directed acyclic graphs (DAGs) arise, they imply that runs cannot loop back to previously visited states.

Acyclicity supports certain analyses and algorithms because it provides a natural notion of ordering: edges progress “forward” in a way that never repeats a configuration.

4.4 Connectivity and underlying undirected perspective

Although state graphs are directed, analyzing the underlying undirected graph can still provide intuition. If two states are connected in the undirected sense, they lie in the same broader region of the graph, even if directed paths may exist only one way.

This perspective is sometimes used in diagnostics and visualization, while directed reachability remains the definitive measure for what can actually happen in the system’s evolution.

5 Analysis techniques

5.1 Traversal methods: BFS and DFS

Two standard graph traversal techniques are:

  • Breadth-first search (BFS): explores neighbors level by level, useful for reachability and shortest unweighted distances.
  • Depth-first search (DFS): explores along a branch until it cannot continue, useful for component discovery, cycle detection, and ordering tasks.

In state graph analysis, traversal is frequently used to compute reachable sets, identify structural properties, and support algorithmic verification tasks.

5.2 Computing shortest paths (when weights exist)

If transitions are associated with weights (for example, costs, times, or step penalties), shortest-path algorithms can compute minimal total weight paths between states.

The relevant choice depends on weight constraints:

  • With nonnegative weights, classical algorithms such as Dijkstra’s method apply.
  • With general settings, other approaches may be used to handle negative values carefully.

When weights are absent, “shortest” is typically interpreted in terms of the minimum number of transitions, which BFS can provide in unweighted graphs.

5.3 Detecting cycles

Cycle detection can be performed efficiently using DFS-based strategies or specialized algorithms for directed graphs. Detecting cycles helps determine whether the system can revisit states, potentially indicating non-terminating behavior.

In practice, cycle detection often complements SCC computation: an SCC with more than one vertex (or a self-loop) indicates the presence of a cycle.

5.4 Topological sorting for acyclic cases

For DAGs, topological sorting produces an ordering of vertices such that every directed edge goes from earlier to later in the list. This ordering reflects the absence of cycles and can be used to:

  • reason about feasible execution order,
  • simplify dynamic programming on the graph, and
  • support scheduling interpretations.

If topological sorting fails to produce a complete order, it signals the presence of a directed cycle.

6.1 Labeled state graphs

In a labeled state graph, edges carry symbols from an alphabet or identifiers for events/inputs. Labeled graphs make it possible to ask input-sensitive questions, such as:

  • which sequences of inputs can lead from one state to another,
  • whether certain patterns are realizable, and
  • how nondeterminism depends on the triggering symbol.

Labeling increases expressiveness at the cost of additional modeling structure.

6.2 State graphs with probabilities (brief overview)

Some state graphs incorporate probabilistic transitions, where each outgoing edge has an associated probability. This supports modeling of random choice, uncertainty, or stochastic systems.

In such settings, reachability often becomes a question about positive probability (“can it happen?”) or about expected quantities (“how long until it happens?”), depending on the analysis goals. The graph remains central, but probabilities refine what “possible” means.

6.3 Relationship to automata theory

State graphs are closely connected to automata theory. Many automata are described as directed graphs of states with transitions labeled by input symbols, where computation corresponds to following transitions according to an input string.

A common conceptual link is to finite-state machines (FSMs): an FSM comprises a finite set of states and rules that map an input at each step to a next state (deterministic FSM) or to multiple possible next states (nondeterministic FSM). Under this correspondence, a state graph serves as the execution skeleton of the machine.

This connection explains why many graph properties—reachability, cycles, SCCs—also matter for language recognition and processing behavior.

6.4 Transition systems as a generalization

Transition systems generalize the state graph idea by formalizing the semantics of transitions more broadly, often including:

  • input alphabets or action labels,
  • sets of states that may be infinite,
  • structured transition relations, and
  • logical or temporal properties to evaluate.

While a state graph is typically a directed graph presentation, a transition system can be viewed as the underlying formal model that state graphs help visualize and compute over.

7 Examples and worked mini-cases

7.1 Simple toggle behavior example

Consider a system with two states: Off and On. The rule is “toggle each step”: from Off the system moves to On, and from On it moves back to Off. The resulting state graph has two vertices and two directed edges forming a 2-cycle.

From an initial state Off, every run alternates deterministically: the system never reaches a stable absorbing mode, because it always transitions to the opposite state.

7.2 Multi-state progression with branching

Suppose a system starts at Idle. If a task arrives, it can transition to either Processing or Queued; then, Processing leads to Done, while Queued may later transition to Processing and then to Done. The state graph contains branching edges out of Idle and reconverging edges near Done.

This structure illustrates nondeterminism: different runs represent different choices or environmental circumstances, yet all successful paths may still reach a common terminal outcome.

7.3 Modeling eligibility/constraint transitions

A system may include a constraint check before an operation is allowed. For example, from Requested the system can go to Approved only if an external condition holds; otherwise, it transitions to Rejected. Modeling such checks in a state graph uses labeled edges or separate states capturing the eligibility status.

The graph’s reachability analysis can then answer questions like “is Approved reachable from Requested?” depending on which transitions are included or which inputs enable them.

7.4 Interpreting a state graph from a rule set

Given informal rules such as:

  1. “When in state A, event x sends the system to B.”
  2. “When in state B, event y sends it to C, and event z returns it to B.”

one can construct a directed labeled graph by creating vertices for A, B, and C and adding edges corresponding to each event rule.

The resulting graph makes the operational behavior explicit: cycles appear immediately where the rules allow returning to an earlier state, and the set of reachable states from a chosen initial state can be computed directly.