Notes on the parallel decomposition theory of finite state machines

We extend existing theory for the parallel decomposition of finite machines (finite automata) to ω-machines and timed machines. The focus for all three is the existence of a structural relationship between the decomposition and the original machine. This is defined in terms of suitable homomorphisms. The homomorphisms also yield inuitively obvious relationships between the languages of accepted words. The theory of decomposition by state partitions obtaining quotient machines is known for finite machines [Hol82, Shi87]. The extensions to ω-machines is straightforward with a suitable choice of acceptance criteria. Muller acceptance criteria [Tho90] seem natural and are used here. A suitable partial order on the partitions leads to a lattice, the minimal elements of which are the natural starting points in locating decompositions. The extension to timed machines [AD94] is not as straightforward. As anticipated clock resetting and constraints prevent a straightforward state based generalisation. Suitable partitions of both states and clocks are required to generate quotient machines. Once again, a suitable partial order leads to a regarding a lattice, the minimal elements of which are natural starting points. The members of the lattice are now pairs of state partitions with clock subsets. Each of the theories is developed alongside a worked example illustrating how the theory is applied. Discussion of the results, their potential applications and areas of concern is interleaved with the results, and is summarised at the end