| |||||||||||||||||||||||||||||||||||||||||||

## HOME## Theory of X-Machines- History of X-Machine Theory
- Physical Description
- When is a function X-computable?
- Monoids and X-machines
## Reference## MOTIVE |
## Monoids and X-MachinesA key feature of X-machine theory is the number of natural constructions that give rise to monoid homomorphisms. Far from being a mathematical curiosity this is an exciting development, for in general, monoids play an important role in the study of real concurrency, and the close relationship between X-machines and monoids therefore points to a currently unexploited role for X-machines in the study of concurrent semantics.
Recall that a semigroup is a set S together with a binary function °: S × S
A semigroup (S,°) is a monoid if there is some two-sided identity element 1 in S identified by the property
A function f: (S, °
It is worth noting also, the easy fact that chaining together two monoid homomorphisms
F: s
## The monoid
Given a set X, we shall write _{X} |

|X| | |Rel|_{X} |

1 | 2 |

2 | 16 |

3 | 512 |

4 | 6.55 × 10^{4} |

5 | 3.35 × 10^{7} |

10 | 1.27 × 10^{30} |

20 | 2.58 × 10^{120} |

30 | 8.45 × 10^{270} |

For x, y in X it is common to see the statement (x, y) Î R Î *Rel _{X}* expressed in various ways, including xR =
y and x R y. More accurately, we define xR to be the set of all y in X for which
(x, y) Î R. Algebraically speaking,

**Lemma.** If S and T are sets, any relation f: S `~~~>` PT induces a monoid
homomorphism f^{U}: PS `---->` PT defined by

for all subsets U of S : Uf ^{U}= U{ uf | u Î U }.( Equ. 5)

**Proof.** Note first that the identity element in both PS and PT is Ø, whence the identity is preserved by
virtue of the convention UØ = Ø. All that remains is to observe that

(U UV) f^{U}

= U{ wf | w Î UUV }

= U{ wf | w Î U }UU{ wf | w Î V }

= Uf^{U}UVf^{U}( Equ. 6)

i.e., f^{U} preserves the "multiplication" in PS.
**Q.E.D.**

If we choose T = X×X, and recall that P(X×X) = *Rel _{X}*, we see that, no matter what the set S,
any relation from S to

x ~ y <===>for somen: x ~_{n}y( Equ. 7)

We've seen that the function °: A `---->` *Rel _{X}* induces a monoid homomorphism
°*: A*

for each subset L of A* : L°* ^{U}= U{ a°* | a Î L }( Equ. 8)

applied to the particular (regular) language L = L(F) recognised by F. It is now a straightforward exercise to verify that

|M| = L°* ^{U}( Equ. 9)

As this equality illustrates, the actual structure of F is irrelevant to our calculations - all that matters is the language recognised, which we shall normally denote |F|. This is why X-machine refinement is particularly tricky. We cannot simply ask that the computed relations of a given machine be preserved during refinement, because refinement concerns the replacement of structural and functional components with other, more closely detailed, components, while the relation |M| has no dependence upon those structures. Rather, refinement has to be defined at a lower, machine dependent, level, or its equivalent.

It's important to notice, also, that whatever the language |F| may be, we can be certain that it is fairly limited in representational scope, because finite state recognisers can only generate regular languages, which are particularly simple in structure. If we allowed X-machines to be defined over more powerful finitary languages, for example Turing-recognisable languages, we might not necessarily be capable of computing any new class of relation, but the computational complexities of doing so might be greatly reduced.

Moreover, restricting ourselves to using A* to represent typical behavioural sequences is by no means justified, especially as the finite-state structure of F imposes the further constraint that A be finite. Ever since Mazurkiewicz demonstrated their relevance to concurrency theory, for example, there has been a clear case for examining the properties of partially commutative monoids [Kir99], and we have argued elsewhere for the significance of infinite alphabets [Sta94]. Moreover, real-time theorists might challenge the need for strings to be finitary at all.

For each set A we first need some canonical construction that associates with the "alphabet" A some monoid A^{@},
whose elements will be the "strings" over A. Moreover, the relationship between A and A^{@} must be such that any
function °: A `---->` *Rel _{X}* is associated in a canonical way with a related monoid
homomorphism °

Typically we would define A^{@} in terms of some function space (A**U**{A})^{Z},
for some ordered space Z which may or may not be independent of A. For example, the standard X-machine choice
A^{@} = A* is essentially the function space

{ a : w _{0}---->(AU{A}) |

(for some n : a(n)={A}) & (for all m,n: a(n)= {A} &m>n==>a(m)={A}) }( Equ. 10)

of sequences over A which eventually become undefined. Likewise, Kwiatkowska & Stannett's research on transfinite (Mazurkiewicz) trace theory, where it was noted that well-ordered observations of real-time processes always generate traces over countable ordinals, focussed on monoids of the form

{ a : w _{1}---->(AU{A}) |

(for some n : a(n)={A}) & (for all m,n: a(n)= {A} &m>n==>a(m)={A}) } / i( Equ. 11 )

It is easy to see that every initial ordinal w generates a corresponding recursion regime. Nor, of course, need we restrict attention to ordinals. Our own TXM constructions rely on the observation that, given any collection of directed spaces D, we can construct suitable D-based monoids based on A.

No matter what recursion regime we select, however, we are assured that each labelling ° induces a monoid
homomorphism °^{@U}: P(A*) `---->` *Rel _{X}* given by

for each subset L of A ^{@}: L°^{@U}= U{ a°^{@}| a Î L }( Equ. 12)

i.e., "languages" over A are mapped in a consistent manner to relations on X. This allows us to ask additional questions concerning computational technologies, e.g., given such-and-such a relation R, for which combination of language type and recursion regime will R be computable?

- X-machines
- Samuel Eilenberg (1974) Automata, Languages and Machines, vol A. Academic Press.

- Mazurkiewicz trace languages as partially commutative monoids
- Daniel Kirsten (1999) On Decision Problems of Recognisable Trace Languages. Ph.D. Thesis, Dresden University of Technology.

- Transfinite Mazurkiewicz traces
- Marta Kwiatkowska & Mike Stannett (1992) On Transfinite Traces. ASMICS Proc. Universitat Stuttgart Fakultat Informatik, Bericht 4/92, 123-57.

- Convergence of Mazurkiewicz traces
- Mike Stannett (1994) Infinite Concurrent Systems - I. The relationship between metric and order convergence. Formal Aspects of Computing 6, 696-715.