XDI State Graph

Definitions

An arrow takes on one of the following two appearances:
[ zoom | xfig ]
Moreover, every arrow is labeled with a terminal identifier. Dashed arrows are called input arrows, representing the occurrence of an input signal on the associated terminal. Similarly, solid arrows are called output arrows, representing the occurrence of an output signal on the associated terminal.

A node takes on one of the following ten appearances:
[ zoom | xfig ]
From left to right, the five shapes are referred to as: top, transient (or nabla), indifferent (or box), demanding (or delta), and bottom. The bold filled versions on the lower line are used for the initial state. Here is an interpretation of the node shapes:

• Top nodes represent a miracle state (to be avoided by the system).
• Transient nodes represent states with an output obligation (to be fulfilled by the system when no input is received).
• Indifferent nodes represent states with neither input nor output obligation,
• Demanding nodes represent states with an input obligation (to be fulfilled by the environment) but no output obligation.
• Bottom nodes represent an error state (to be avoided by the environment).

Finally, there are some syntactic restrictions on XDI state graphs:

1. Arrows are labeled consistently (w.r.t. appearance); that is, every terminal identifier either appears on input arrows only, or on output arrows only.
2. There is exactly one initial node (bold filled node).
3. For every node, the arrows leaving that node have distinct labels.
4. All nodes have identical sets of outgoing arrow labels.
5. Every node is reachable from the initial node via a path of zero or more arrows.
6. A transient node has at least one outgoing output arrow.
7. A demanding node has at least one outgoing input arrow.
8. An input arrow to a top node comes from a top node.
9. An output arrow to a bottom node comes from a bottom node.
10. Arrows from a top node only go to a top node.
11. Arrows from a bottom node only go to a bottom node.
12. They are minimal as explained below.
13. They satisfy the Extended JTU Rules.

Restrictions 2 and 3 expresses that the state graph is unambiguous. Restriction 4 expresses that the state graph is complete. Restriction 5 expresses that the state graph is connected.

Minimality

Figures of XDI state graphs

Implied arrows and nodes

As a consequence of leaving certain arrows and nodes implicit, a figure of an XDI state graph appears to violate restriction 4. "Missing" arrows and nodes can be reconstructed as follows. Whenever a node lacks a certain outgoing input arrow this arrow should be added going to a bottom node, which should be added if not already present. Similarly, whenever a node lacks a certain outgoing output arrow this arrow should be added going to a top node, which should be added if not already present.

Implied arrow labels

Node numbers

Nodes with the same number are one and the same node (having the same appearance in all occurrences) and all their incoming and outgoing arrows should be "taken together". An arrow pointing to just a number is understood to point to the node with that number (such a node should appear somewhere in the figure).

XDI format

Name:
  <name>
Terminals:
  <terminal list>
InitialState:
  <state>
States+Arrows:
  ( <state> <state label> <transition list> )*

  <terminal list> ::= <empty>
    | <terminal> <direction> <terminal list>
  <terminal> ::= <identifier>
  <direction> ::= ? | !
  <state> ::= <identifier>
  <state label> ::= > | # | <
  <transition list> ::= <empty>
    | <terminal> : <state> <transition list>

?

labels an input terminal

!

labels an output terminal

>

labels a transient state

#

labels an indifferent state

<

labels a demanding state

Each state is labeled by a unique identifier, usually a number. The label of the bottom state is BOT and of the top state it is TOP.

Last modified at Mon Oct 26 16:08:03 1998