3 - Transition systems

Summary

Transition-system spaces

This chapter introduces the semantic domain that is used throughout this book. The goal is to model reactive systems; the most important feature of such systems is the interaction between a system and its environment. To describe such systems, the well-known domain of transition systems, process graphs, or automata is chosen. In fact, it is the domain of non-deterministic (finite) automata known from formal language theory. An automaton models a system in terms of its states and the transitions that lead from one state to another state; transitions are labeled with the actions causing the state change. An automaton is said to describe the operational behavior of a system. An important observation is that, since the subject of study is interacting systems, not just the language generated by an automaton is important, but also the states traversed during a run or execution of the automaton. The term ‘transition system’ is the term most often used in reactive-systems modeling. Thus, also this book uses that term.

The semantic domain serves as the basis for the remainder of the book. The meaning of the various equational theories for reasoning about reactive systems developed in the remaining chapters is defined in terms of the semantic domain, in the way explained in the previous chapter. Technically, it turns out to be useful to embed all transition systems that are of interest in one large set of states and transitions, from which the individual transition systems can be extracted.