W3C

XTND - XML Transition Network Definition

W3C Note 21 November 2000

This Version:
http://www.w3.org/TR/2000/NOTE-xtnd-20001121
Latest version:
http://www.w3.org/TR/xtnd
Editors:
Gavin Thomas Nicol, Chief Scientist, eBusiness Technologies, Inc.

Abstract

In many systems, transition networks are used to describe a set of states and the transitions that are possible between them. Common examples are such things as ATM control flows, editorial review processes, and definitions of protocol states. Typically, each of these transition networks has it's own specific data format, and it's own specific editing tool. Given the rapid transition to pervasive networking, and to application integration and interchange, a standard format for transition networks is desirable. This document defines such an interchange format, defined in XML: the interchange language for the Internet.

Status of This Document

This document is one component of a submission request to the World Wide Web Consortium from eBusiness Technologies, Inc. (see Submission Request, W3C Staff Comment). For a full list of all acknowledged Submissions, please see Acknowledged Submissions to W3C.

This document is a Note made available by W3C for discussion only. This work does not imply endorsement by, or the consensus of the W3C membership, nor that W3C has, is, or will be allocating any resources to the issues addressed by the Note. This document is a work in progress and may be updated, replaced, or rendered obsolete by other documents at any time.

This document is submitted to the W3C in the hope that it will serve an educational and advisory role for future efforts.

Should any changes be required to the document, we would expect future versions to be produced by the W3C process. eBT maintains ownership of the XTND specification and reserves the right to maintain and evolve the XTND specification independently and such independent maintenance and evolution shall be owned by eBT.

A list of current W3C technical documents can be found at the Technical Reports page.


Table of Contents


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:

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:

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.

Depication of the 'data ready' state.

Depiction of the "data ready" state

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

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:

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

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:

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

Start and End state diagram

Start and End state diagrams.

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.

Sample transition from 'cold' to 'hot'

Sample transition from "cold" to "hot"

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:

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:

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:

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.

Augemented symbols for representing conditions and actions

Augmented symbols for representing conditions and actions

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:

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.

Simple transition network for a door

Simple transition network for a door

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.

Transition network with actions

Transition network with actions

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

Glossary

Action
An operation associated with a state transition that interact with objects in the environment of the transition network.
Active State
A state that represents a continuum of behavior. For example closing the door represents an active state.
Condition
A predicate controlling the ability to transition from one state to another.
End State
A state that has no forward transitions possible.
Event
An action that is sent outside the local environment of the transition network. Events are one means of having transition networks affect larger system state.
Data Flow Diagrams
A diagramming technique showing how data flows through a set of states.
Finite State Machines
An abstract machine that is made from a set of states and transitions between then. FSMs are typically said to "match their input" in the set of input results in no transitions to error states. Unlike transition networks, FSMs do not explicitly provide the notion of actions.
Forward Transition
A transition out of a given state.
Guard
A predicate controlling the ability to transition from one state to another. See Condition.
Message
An action that is sent outside the local environment of the transition network. See Event.
Operation
Something associated with a transition that allows the transition network to define interaction with it's environment.
Passive State
A state which, when entered, is fully transitioned into.
Preconditions
A set of conditions controlling entry into a state, or the traversal of a transition.
Prelude
A set of actions executed upon entry into a state.
Postconditions
A set of conditions controlling whether it is possible to leave a state.
Postlude
A set of action executed when a state is exited.
Process
A form of state transition network.
Static State
A state which, when entered, is fully transitioned into. See Passive State.
Transition Network
A network of states and the transitions between them. Unlike FSMs, transition networks describe actions that can occur in the network.
XTND
An XML definition of a transition network. XTND is pronounced "eXTeND".

Bibliography

The following is a list of recommended reading.

Diagramming Techniques for Analysts and Programmers
J. Martin and C. McClure
Object Oriented System Development
Dennis de Chapeaux, Douglas Lea, Penelope Faure
XML 1.0
http://www.w3.org/XML