When discussing languages, say, in the theory of finite automata?, the usual starting point is a set, , of symbols, which is taken to be the alphabet for the language. The next step is to form the free monoid, , on the alphabet, and then a language is simply a subset of , and these can be used in a number of situations to describe the workings of a ‘system’, the symbols being used to represent certain operations or actions of the system, and the words in thus corresponding to sequences of operations. Usually the system will not allow arbitrary sequences of operations to be performed, and so the system determines a language, namely the allowable execution sequences. Describing the language, helps describe and determine the overall ‘system’.
If the system being studied has some concurrency in it, so that certain of the operations are (causally) independent of each other, then one way of modelling such a system is to use a (Mazurkiewicz) trace alphabet, that is one in which the independence is explicitly taken into consideration.
A (Mazurkiewicz) trace alphabet is a pair where is a (usually finite) set of actions and is an irreflexive and symmetric relation.
The relation is usually referred to as independence. Its complement is called the dependency relation. It will be reflexive and symmetric. (Such a sense of ‘dependency relation’ is interpreted in a related but slightly different way from that in the use of dependency graphs in project planning.)
Consider the following ‘dependency diagram, with some vertices (states) and labelled edges (actions):
(arrow go from left to right but are not showing up … bother!)
We take and note that, starting at the left, depends on (written , since we cannot start action until action has been completed. This gives a labelled poset.
Here the first information to encode in is the poset structure of dependency
then symmetrise this, and take the complement to get
Note this encoding does not involve the relationship given by adjacency, and hence ignore if an ‘execution sequence’ is ‘allowable’ (i.e., realistic) so is in even though we could not first ‘do’ and then ‘do’ (unless of course had already been done).
The language (trace language?) corresponding to the model will be a subset of the trace monoid of the trace alphabet given here. It will encode allowable execution sequences but also will consider the allowable sequences ( traces ): , , , etc. to be identified.