An Introduction to CSXMS Models
This page attempts to provide a brief introduction to what
are, and where their development has got to. The other aspects of
these models, for which there are separate pages, are as follows.
- The papers and other
them, which provide more detail of the aspects described here.
- The different variants of the
that have evolved.
The rest of this page is divided into the following sections.
The Background to CSXMS Models
The Aim of CSXMS Models ;
The Structure of CSXMS Models ;
The Links Between CSXMS and Data Flow
The Background to CSXMS Models
CSXMS Models have been developed from the basic computational
known as an X-Machine.
This model was developed originally by the American mathematician
Eilenberg, and although he referred to it as the X-machine model, it
now been suggested that they should be known instead as Eilenberg
in his honour, and this name is gradually being adopted. You
however, find both names being used here.
The distinguishing feature of an Eilenberg machine is that it has
a finite state automaton, which models the control of the
within the machine;
a memory, which describes the data structure on which the
is performed by the machine;
an input tape and an output tape, which describe
the data accepted by the machine and the results that it
a set of processing functions, which describe the
in which the computation is performed by the machine.
The linkage between these components then has two parts.
- Each processing function defines how the combination of
values and the symbols
available on the tapes is mapped into new
values and symbols on the tapes.
- Each transition of the finite state automaton depends on the
of the memory and the symbols
available on the input tape, and is
with one of the processing functions, which is applied when that
There a large number of different versions of this model, and there is
not space here to review them. One of the most important versions
is the stream X-machine, which imposes the following limitations on the
behaviour of each transition function.
The effect of these limitations is that each tape therefore functions
a stream of data - hence the name. Stream X-machines have many
properties, which there is not space to review here, and in particular
there are important properties related to the generation of test sets
such models. These mean that, if the individual processing
have been completely tested, then under certain conditions one can
a set of tests which will guarantee that their integration into a
X-machine has been completely tested, so that the resultant system has
been completely tested, too.
- The only symbol on the tapes on which this function may depend is
head of the input tape.
- The function must change the input tape by removing this head
may not make any other change to it.
- The function must change the output tape by appending a symbol to
but may not make any other change to it.
For more information about the X-machine models, see the pages dealing
with them that have been created by Mike Holcombe
and by Mike Stannett.
The Aim of CSXMS Models
Given this background, the aim of a CSXMS model is really quite
One stream X-machine can model quite a complex piece of software, as in
principle any of the processing functions of an Eilenberg machine could
be defined in terms of the input-output computation performed by
Eilenberg machine, so that the machines can be assembled
Any such hierarchical composition of the machines will, however, only
a single automaton (albeit a complex one), and so it is not really
to model a distributed system in which there are a number of
processing proceeding concurrently.
Hence, the aim of the CSXMS (Communicating Stream X-Machine Syatem)
model is, as its name suggests, to extend this model to a system of
communicating processes. In doing this, the assumption is that
individual process will be modelled in terms of a single Eilenberg
(usually a stream X-machine, but for some purposes it is convenient to
relax some of the stream restrictions), so that by adding a suitable
of the communication mechanism a complete system can be represented.
The Structure of CSXMS Models
There are a number of different variants of the basic CSXMS model, and
these are described separately, but the common feature of all of them
that they have three components.
The structure that is usually used to model the communication mechanism
is a matrix (usually called the communication matrix) whose
function as uni-directional communication buffers between the different
individual machines. Typically there will also be associated with
these special variables in the memory of each machine, known
as that machine's input port and output port, and the
set of processing functions in each machine are then augmented by communication
functions, which will either write values from the output port into
an element of the communication matrix or read values from the
matrix into the input port.
- The set of individual Eilenberg machines which model the
- Some structure involving the individual input and output tapes,
to represent the input to and output from the complete system.
- Some structure that models the mechanism by which the individual
machines communicate with each other.
The Links Between CSXMS and Data Flow Algebra
An important theoretical result for CSXMS is that, for any CSXMS, it is
possible to construct an equivalent stream X-machine. This means
that in principle it should be possible to extend the testing results
ordinary Eilenberg machines to CSXMS. In practice, though, the
of the state space for such an equivalent stream X-machine is such that
the number of states explodes combinatorially, and hence so to would
complexity of the testing process.
Since a CSXMS is defined essentially in terms of processes
communicate via data channels (ie the elements of the communications
then it should be apparent that its static structure can be represented
in terms of a data flow diagram. Hence, if one had a suitable
of the allowable sequences of communications between the different
in the system, it should be possible to model this in terms of a data
flow algebra (DFA) description. An important aspect of this
is currently being investigated is whether it can be used to guide the
testing process, so as to avoid the effects of the combinatorial
of the state space.
From what has been said above, it will be obvious that there is still a
lot to do, in areas such as:
investigating further the theoretical properties of
developing applications of the models to case studies of system
developing the linkages with DFA.
More detailed proposals for some of these developments are set out in my projects page
This page created by A.
Cowling, and last updated on 11 August 2004