An Introduction to CSXMS Models

This page attempts to provide a brief introduction to what CSXMS models 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 publications about them, which provide more detail of the aspects described here.
The different variants of the basic model 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 Algebra ;

Future Developments.

The Background to CSXMS Models

CSXMS Models have been developed from the basic computational model known as an X-Machine. This model was developed originally by the American mathematician Samuel Eilenberg, and although he referred to it as the X-machine model, it has now been suggested that they should be known instead as Eilenberg Machines in his honour, and this name is gradually being adopted. You will, however, find both names being used here.

The distinguishing feature of an Eilenberg machine is that it has four components:

a finite state automaton, which models the control of the computation within the machine;

a memory, which describes the data structure on which the computation is performed by the machine;

an input tape and an output tape, which describe respectively the data accepted by the machine and the results that it produces; and

a set of processing functions, which describe the primitive steps 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 the current memory values and the symbols available on the tapes is mapped into new memory values and symbols on the tapes.
Each transition of the finite state automaton depends on the current values of the memory and the symbols available on the input tape, and is associated with one of the processing functions, which is applied when that transition occurs.

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 only symbol on the tapes on which this function may depend is the symbol at the head of the input tape.
The function must change the input tape by removing this head symbol from it, but may not make any other change to it.
The function must change the output tape by appending a symbol to the tail of it, but may not make any other change to it.

The effect of these limitations is that each tape therefore functions as a stream of data - hence the name. Stream X-machines have many useful properties, which there is not space to review here, and in particular there are important properties related to the generation of test sets from such models. These mean that, if the individual processing functions have been completely tested, then under certain conditions one can generate a set of tests which will guarantee that their integration into a stream X-machine has been completely tested, so that the resultant system has been completely tested, too.

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 simple. 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 another Eilenberg machine, so that the machines can be assembled hierarchically. Any such hierarchical composition of the machines will, however, only be a single automaton (albeit a complex one), and so it is not really adequate to model a distributed system in which there are a number of communicating 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 concurrent communicating processes. In doing this, the assumption is that each individual process will be modelled in terms of a single Eilenberg machine (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 model 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 is that they have three components.

The set of individual Eilenberg machines which model the individual processes.
Some structure involving the individual input and output tapes, in order to represent the input to and output from the complete system.
Some structure that models the mechanism by which the individual Eilenberg machines communicate with each other.

The structure that is usually used to model the communication mechanism is a matrix (usually called the communication matrix) whose elements 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 respectively as that machine's input port and output port, and the normal 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 communication matrix into the input port.

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 for ordinary Eilenberg machines to CSXMS. In practice, though, the construction 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 the complexity of the testing process.

Since a CSXMS is defined essentially in terms of processes which communicate via data channels (ie the elements of the communications matrix), 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 description of the allowable sequences of communications between the different processes in the system, it should be possible to model this in terms of a data flow algebra (DFA) description. An important aspect of this which is currently being investigated is whether it can be used to guide the testing process, so as to avoid the effects of the combinatorial explosion of the state space.

Future Developments

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 CSXMS models;

developing applications of the models to case studies of system designs;

developing the linkages with DFA.

More detailed proposals for some of these developments are set out in my projects page .

Jump Back to a section of this page:

Introduction (ie the top of the page);
Contents ;
The Background to CSXMS Models ;
The Aim of CSXMS Models ;
The Structure of CSXMS Models ;
CSXMS and DFA ;
Future Developments .

Go to main CSXMS page;
Go to other CSXMS pages:

For papers;
For variants ;

Go to my projects page ;
Go to Personal Page.