Dykstra's projection algorithm

In computer science, specifically in the field of formal verification, well-structured transition systems (WSTSs) are a general class of infinite state systems for which many verification problems are decidable, owing to the existence of a kind of order between the states of the system which is compatible with the transitions of the system. WSTS decidability results can be applied to Petri nets, lossy channel systems, and more.

Formal definition

Recall that a well-quasi-ordering $\le$ on a set $X$ is a quasi-ordering (i.e., a reflexive, transitive binary relation) such that any infinite sequence of elements $x_0,x_1,x_2,\dots$, from $X$ contains an increasing pair $x_i\le x_j$ with $i<j$. The set $X$ is said to be well-quasi-ordered, or shortly wqo.

For our purposes, a transition system is a structure $\mathcal{𝒮}=⟨S,\to ,\cdots ⟩$, where $S$ is any set (its elements are called states), and $\to \subseteq S\times S$ (its elements are called transitions). In general a transition system may have additional structure like initial states, labels on transitions, accepting states, etc, but they do not concern us here.

A well-structured transition system consists of a transition system $⟨S,\to ,\le ⟩$, such that

• $\le \subseteq S\times S$ is a well-quasi-ordering on the set of states.
• $\le$ is upward compatible with $\to$: that is, for all transitions $s_1\to s_2$ (by this we mean $(s_1,s_2)\in \to$) and for all $t_1$ such that $s_1\le t_1$, there exists $t_2$ such that $t_1\stackrel{*}{\to }{t}_2$ (that is, $t_2$ can be reached from $t_1$ by a sequence of zero or more transitions) and $s_2\le t_2$.

References

• A. Finkel and Ph. Schnoebelen, Well-Structured Transition Systems Everywhere!, Theoretical Computer Science 256(1–2), pages 63–92, 2001.