Introduction to Transition Networks

People often talk about processes; a sequence of events that have occurred. Typical descriptive sentences will be of the form "First this happens, then this happens. After that, if this condition is true, that happens". For communicative purposes between people, such sentences suffice, but for computers, a more formal approach is needed. One such formalism is the notion of a transition network.

What are transition networks?

Loosely speaking, a transition network is a set of states and the transitions between them. As noted above, they are good at capturing the notion of process. For example:

• Control processes such as those in a digitally controlled heating system.
• Processes controlling manufacture or design.
• Workflow processes such as those found in product data management software.

They are also useful in modeling the behavior of systems and can be used in object-oriented analysis to create formal models of object interaction and larger system behavior.

Transition networks are closely related to finite state machines(FSM) , and to data flow diagrams(DFD), but they are augmented with the following capabilities:

• Transition networks are not limited to "accepting or rejecting their input". Transition networks may execute actions or fire off events during transitions.
• Transition networks can interact with other objects, thereby affecting change in the transition network (or in other networks).
• Transitions in transition networks can be controlled by guard conditions that prohibit or allow the transition to be followed.
• These guard conditions can be dependent on any predicate involving objects from within the environment of the transition network.

As such, transition networks can be used to describe far more complex interactions or processes than either FSMs or DFDs allow.

What are states?

A state within a transition network can loosely be defined as a point between transitions. In transition network diagrams, a state is typically depicted as a circle containing the name of the state, as show below.

While states are a point between transitions, there are some advantages to dealing with them explicitly:

• Talking about states forms part of normal conversion. For example, people say, "my engine is off" meaning that the engine is in the off state. The principals of natural design call for states to be modeled explicitly.
• There can often be multiple transitions into, and more importantly, out of, a state. As such, states can represent a branch in a process.
• In some transition network formalisms, entry and exit from states can also execute actions and generate events.

Typically states are defined in terms of the attributes of an object, or objects in the system. For example, one would say that water has a number of states:

• Frozen - when the temperature of the water is less than 0 degrees.
• Cold - when the temperature is less than 32 degrees.
• Hot - when the temperature is greater than 80 degrees.
• Boiled - when the temperature is greater than 100 degrees.

One might also have the state "normal" as defined below.

• Normal - The state is not Frozen, Cold, Hot or Boiled.

The important point about the last example is that it shows one of the requirements of states: that they be exclusive. An object, or system, cannot be in two states at once.

Active and passive states

In many processes, there is the notion of continuum, which is not completely captured by the above definition of state. For example, we have the notion of "thawing", where the word implies an ongoing, and active state that is continually altering the system. This will be discussed further in the section on transitions.

Start and End states

Even though the process may allow entry and exit from multiple states, when describing the execution of a process, there is always a beginning, and an end. Transition networks, likewise, require start and ending states. Start and end states can be defined as follows:

• Start state - a state that, in the context of a given execution, has no transitions preceding entry into the state.
• End state - a state that has no transitions out of the state (no forward transitions).

For the rest of this paper, the following two symbols will be used.

Note that this differs from traditional data flow diagram symbols.

What are transitions?

A transition is an atomic, directed connection between one state and another. Typically transitions are represented as a line connecting two states. The following is a simple example.

Bi-directional transitions (transitions both from a to b and b to a) are typically modeled as two separate transitions.

Transitions can be defined implicitly by the exclusionary nature of states: when the conditions defining one state become false, and the conditions for another true, there is an implicit transition from one state to another; this model has only limited applicability however.

Transitions and Active States

An active state can be looked upon as a state that is being continually updated, or a gradual transitionfrom one state to another. As such, active states can be looked upon as a form of continually evaluated transition.

While using transitions to model active states does not capture the full semantics (because they are atomic, and not continually updated), for most purposes this model suffices to capture the distinction.

Note that in fact it is often useful to think at an even finer level of granularity, and break transitions down into 3 discrete steps that form an atomic action. Those steps are:

• Leaving a state - the point at which the state has been left, but traversal of the transition between states has not yet begun.
• Transitioning between states - the act of traversing the transition between states.
• Entering a state - the point at which the new state is entered, but before the "resting point" has been reached.

These 3 steps can, of course, be decomposed into a transition network.

Conditions, Actions and Events

The main thing separating transition networks from FSM is their active nature. This is captured in the notion of conditions, actions, and events.

Conditions

In order to control the set of transitions that are possible within a transition network, it is necessary to introduce the notion of a condition . Essentially a condition is a set of predicates that guard entry to and/or exit from a given state. In other words, conditions filter the set of possible transitions.

In some systems, the conditions are placed solely on the transitions themselves, in others conditions can be placed upon states as a precondition to entry. These are essentially the same thing, and are not mutually exclusive: in a system allowing both, the union of the guard conditions on the transition and the preconditions on the state form the total set of conditions to be met (i.e. this is an implicit "and" combination of the predicates). Likewise, it is possible to have postconditions on a state controlling the ability to transition from a state.

Given the above, there are three types of conditions found in transition network systems:

• State preconditions - conditions that guard entry into a state.
• State postconditions - conditions that guard exit from a state.
• Transition preconditions - conditions guarding the transition from one state to another.

Actions

In transition networks actions , or operations , allow processing to be associated with a transition. Typically such actions will involve simple interaction with objects in the environment of the transition (getting and setting properties typically), though any arbitrary processing can be performed within the context of the environment. One rule must be obeyed however: altering the environment such that the guard conditions would now fail, should not result in the transition failing. Transitions must always be regarded as atomic.

Typically, actions are associated with the transition, but it is often desirable to be able to specify actions at each of the three steps involved in making a transition. As such, there are three sets of actions that can be invoked:

• State postlude - the set of actions associated with the exit from a state.
• Transition body - the set of actions associated with transition traversal.
• State prelude - the set of actions associated with the entry into a state.

Events

Actions are scoped to the environment in which they are executed, and so they can only affect local state. Events , or messages, represent the interaction of the transition network with objects outside the local scope. Typically, they are modeled as actions that have the ability to send an event.

Diagramming Conditions, Actions and Events

In order to capture conditions and actions in a diagram (again, events are modeled as actions capable of sending an event), we must augment the symbols given above. The augmented version shown below will be used throughout the rest of this document.

Encoding Transition Networks in XML

Transition networks form a graph, and XML is hierarchical, so there would appear to be some discord between the two models. This is not the case if a transition network is seen as a set of states, and a set of transitions: these sets can be easily marked up in XML. Following the practice of natural design leads to a fairly natural mapping from this view of a transition network to its XML representation. This section describes that mapping.

Marking up States

From the explanations in the introduction, states can be modeled as objects with the following type:

state = object {
  name           = string;
  preconditions  = set of predicates;
  prelude        = ordered set of actions;
  postconditions = set of predicates;
  postlude       = ordered set of actions;
};

Translating this into XML yields a simple element definition as shown below.

<!ELEMENT state  (properties?, 
                  preconditions?, 
                  prelude?, 
                  postlude?, 
                  postconditions?) >

<!ATTLIST state id   ID    #REQUIRED
                name CDATA #REQUIRED >

The properties, preconditions, postconditions, prelude and postlude elements are defined elsewhere.

The 2 main things to note about this definition of a state are:

1. The id attribute - this is declared as an ID attribute to guarantee that the state identifier is unique throughout the transition network definition.
2. The name attribute - provides a descriptive name for the state.

Marking up Transitions

Like states, the introduction provides the basis for deriving an object type for transitions. A transition can be modeled as:

transition = object {
  from           = oid;
  to             = oid;
  preconditions  = set of predicates;
  actions        = ordered set of actions;
};

Translating the object into XML once again yields a straightforward element definition, as shown below.

<!ELEMENT transition  (properties?, 
                       preconditions?, 
                       actions?) >

<!ATTLIST transition id         ID            #REQUIRED
                     name       CDATA         #REQUIRED
                     from       IDREF         #REQUIRED
                     to         IDREF         #REQUIRED
                     mode       (auto|manual) #REQUIRED>

As for state definitions, the properties, preconditions, and actions elements are defined elsewhere.

The main things to note about this element definition are:

• The id attribute - this is declared as an ID attribute to guarantee that the transition identifier is unique throughout the transition network definition.
• The name attribute - provides a descriptive name for the transition.
• The to and from attributes - these form the connection between states. They are defined as IDREF attributes so that they are constrained to reference the id attribute of a state (though this constraint is cannot be enforced by the DTD alone).
• The mode attribute - this states whether the transition should be taken automatically if the set of conditions allows it. If this is set to auto, the transition will be taken automatically, if it is set to manual, an event of some sort will be needed to force the transition.

Marking up Actions

One of the great challenges in using transition networks is modeling actions. Typically, behavior in systems is defined in a procedural manner rather than declaratively: in other words, actions are defined in terms of how they are to be performed, rather than what effect the actions will have. This is largely because, as yet, purely declarative systems that can model complex interactions remain a research problem.

As such, the approach taken here to use an expression language defined in XML, but to model behavior at a coarse level rather than a fine-grained procedural level. As an example, rather than specifying how an event is sent, a <send-event> expression would be defined. Within the context of a given application, these coarse-grained actions, if defined well, can be seen as declarative, and a degree of static analysis becomes possible.

The language chosen here is the XEXPR language, an example of which follows.

  <set name="AA" value="AA Value"/>
  <print newline="true"><get name="AA"/></print>

Preconditions, Postconditions, Prelude, Postlude and Actions

In the element definitions for states and transitions, a number of other elements were defined. There declarations follow:

<!ELEMENT preconditions  (%expression;)*>
<!ELEMENT postconditions (%expression;)*>
<!ELEMENT prelude        (%expression;)*>
<!ELEMENT postlude       (%expression;)*>
<!ELEMENT actions        (%expression;)*>

They all use a list of expressions. For conditions, expressions are restricted to predicates. The use of a parameter entity makes it easy to extend the set of possible expressions as the XEXPR language allows elements to be bound to expressions, meaning that the base DTD may not model all elements in the definition.

Definitions For XML Transition Networks

The following is the complete set of definitions from the DTD for XTND along with explanatory prose.

<!DOCTYPE xtnd [


<!ENTITY % def.prop PUBLIC "-//EBT//ELEMENTS Property Set//EN">
%def.prop;


<!ENTITY % def.expr PUBLIC "-//EBT//ELEMENTS XML Expression Language//EN">
%def.expr;

This starts the DTD, and pulls in two DTD modules: the property and expression definitions. The public identifier for the DTD is "-//EBT//DTD Transition Network//EN"

<!ELEMENT preconditions  (%expression;)*>
<!ELEMENT postconditions (%expression;)*>

Preconditions and postconditions are simply a set of predicates (expressions that evaluate to a Boolean result). The expression parameter entity is defined in the def.expr module.

<!ELEMENT xtnd (properties?, 
               definitions?, 
               states, 
               transitions?)>
<!ELEMENT definitions (define*)>

A transition network can optionally have an arbitrary set of properties associated with it that, depending on the application, could either be used as metadata, or form part of the execution environment of the objects in the system.

In addition, a transition network can optionally have a set of definitions. This is simply a list of <define> expressions from the XEXPR language that allow elements to be bound to expressions for use in actions. See the XEXPR specification for more detail.

The heart of the transition network is made up of a required set of states, and an optional set of transitions.

<!ELEMENT states (state+)>
<!ATTLIST states start IDREF #REQUIRED>
<!ELEMENT state  (properties?, 
                  preconditions?, 
                  prelude?, 
                  postlude?, 
                  postconditions?)>
<!ATTLIST state id   ID    #REQUIRED
                name CDATA #REQUIRED>


<!ELEMENT prelude  (%expression;)*>
<!ELEMENT postlude (%expression;)*>

The set of states is simply a list of <state> elements. Each state must have a unique ID attribute and a descriptive name attribute. As part of the state, each state can have an optional set of preconditions, an optional set of postconditions, an optional prelude, and an optional postlude. All of these can contain a list of expressions.

There must be a single start state defined in the network, identified by the start attribute on the <states> element.

<!ELEMENT transitions (transition*) >
<!ELEMENT transition  (properties?, 
                       preconditions?, 
                       actions?) >
<!ATTLIST transition id         ID            #REQUIRED
                     name       CDATA         #REQUIRED
                     from       IDREF         #REQUIRED
                     to         IDREF         #REQUIRED
                     mode       (auto|manual) #REQUIRED>
<!ELEMENT actions (%expression;)* >

The set of transitions is an optional, possibly empty list of <transition> elements defining how states can be connected.

XTND Examples

The following are a few examples of transition networks marked up using XTND. As can be seen, the modeling is fairly natural and intuitive in practice.

Simple transition network

The following shows the transition network for a door, which can have only two states: open and closed. The door can transition from open, to closed, and from closed to open. The door starts off in the open state.

This simple transition network can be straightforwardly marked up in XTND as follows.

<xtnd>
<states start="open">
  <state id="open"   name="Opened State"/>
  <state id="closed" name="Closed State"/>
</states>


<transitions>
  <transition id="open-close" 
              name="Transition from opened to closed"
              from="open"
              to="closed"
              mode="manual"/>
  <transition id="close-open" 
              name="Transition from closed to opened"
              from="closed"
              to="open"
              mode="manual"/>
</transitions>
</xtnd>

Note that the mode attribute for both the open and closed states are set to manual. If these were set to auto, it would imply the door opening and closing ad infinitum! As it is, some event must cause the transition.

Adding actions

The above can be augmented with actions. In the diagram below we show that an action is associated with the prelude of each state, and with the transitions between states.

This can also easily be represented in the XML form, as shown below.

<xtnd>
<definitions>
  <define name="enter" args="x">
    <print>Entering <x/>...</print>
  </define>
  <define name="leave" args="x">
    <print>Leaving <x/>...</print>
  </define>
  <define name="t" args="x">
    <print>Transitioning <x/>...</print>
  </define>
</definitions>

<states start="open">
  <state id="open" name="Opened State">
    <prelude><enter>open</enter></prelude>
    <postlude><leave>open</leave></postlude>
  </state>

  <state id="closed" name="Closed State">
    <prelude><enter>closed</enter></prelude>
    <postlude><leave>closed</leave></postlude>
  </state>
</states>

<transitions>
  <transition id="open-close" 
              name="Transition from opened to closed"
              from="open"
              to="closed"
              mode="manual">
    <actions><t>open-closed</t></actions>
  </transition>
  <transition id="close-open" 
              name="Transition from closed to opened"
              from="closed"
              to="open"
              mode="manual">
    <actions><t>closed-open</t></actions>
  </transition>
</transitions>
</xtnd>

This example also shows the use of definitions, which implies that the expression DTD has also been updated to encompass the defined elements.

Additional DTD Fragments

Namespace

The namespace for XTND is

http://www.ebt.com/xtnd

People using this namespace are encouraged to use the xtnd namespace prefix.

Public Identifier

The public identifier for the XTND DTD is

-//EBT//DTD Transition Network/EN

DTD Fragment for Properties

The following is the DTD fragment for properties in the XTND DTD.

<!ENTITY % properties "properties">
<!ELEMENT properties (property*)>
<!ELEMENT property (#PCDATA)>
<!ATTLIST property 
           name  CDATA                 #REQUIRED
           type  (int|float|boolean|
                  string|object)       #REQUIRED>

The constraints placed on the format of the object values are as follows:

int

[+\-]?[0-9]+

float

[+\-]? [0-9]+.[0-9]+[+-][eE][0-9]+

boolean

true|false

string

Any sequence of characters legal as PCDATA. CDATA sections may also be used to escape the textual content.

object

The exact format is application dependent. In Java this might be a BASE64 encoded form of the serialized object.

The public identifier for this fragment is

-//EBT//ELEMENTS Property Set//EN

DTD Fragment for Expressions

The following is a DTD fragment for expressions in the XTND DTD. Note that this will need to be extended for each element defined using the <define> function.

<!ENTITY % expression "bind|define|get|set
                       |expr|add|subtract|multiply
                       |divide|string|integer|float
                       |true|false|nil|eq|neq|leq
                       |geq|lt|gt|and|or|not|if
                       |switch|do|while|print
                       |println">


<!ELEMENT bind EMPTY>
<!ATTLIST bind class CDATA #REQUIRED
               name  CDATA #IMPLIED>


<!ELEMENT define (%expression;)*>
<!ATTLIST define name CDATA #REQUIRED
                 args CDATA #IMPLIED>


<!ELEMENT get EMPTY>
<!ATTLIST get name CDATA #REQUIRED>


<!ELEMENT set (%expression;)*>
<!ATTLIST set name CDATA #REQUIRED>


<!ELEMENT expr (%expression;)*>


<!ELEMENT add (%expression;)*>
<!ELEMENT subtract (%expression;)*>
<!ELEMENT multiply (%expression;)*>
<!ELEMENT divide (%expression;)*>
<!ELEMENT string (#PCDATA)>
<!ELEMENT integer (#PCDATA)>
<!ELEMENT float (#PCDATA) >
<!ELEMENT true EMPTY>
<!ELEMENT false EMPTY>
<!ELEMENT nil EMPTY>
<!ELEMENT eq (%expression;)*>
<!ELEMENT neq (%expression;)*>
<!ELEMENT leq (%expression;)*>
<!ELEMENT geq (%expression;)*>
<!ELEMENT lt (%expression;)*>
<!ELEMENT gt (%expression;)*>
<!ELEMENT and (%expression;)*>
<!ELEMENT or (%expression;)*>
<!ELEMENT not (%expression;)*>
<!ELEMENT if (%expression;)*>
<!ELEMENT switch   (case*) >
<!ELEMENT case (%expression;)*>
<!ELEMENT do (%expression;)*>
<!ELEMENT while (%expression;)*>
<!ELEMENT print (#PCDATA|%expression;)*>
<!ATTLIST print newline (true|false) #IMPLIED>
<!ELEMENT println (#PCDATA|%expression;)*>

The public identifier for this fragment is

-//EBT//ELEMENTS XML Expression Language//EN