Notes on the parallel decomposition theory of finite state machines

dc.contributor.authorMason, Kahnen
dc.date.accessioned2013-10-07T04:20:58Z
dc.date.available2013-10-07T04:20:58Z
dc.date.issued1998en
dc.description.abstractWe 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.en
dc.identifier.urihttp://hdl.handle.net/10092/8419
dc.identifier.urihttp://dx.doi.org/10.26021/2140
dc.language.isoen
dc.publisherUniversity of Canterbury. Computer Scienceen
dc.relation.isreferencedbyNZCUen
dc.rightsCopyright Kahn Masonen
dc.rights.urihttps://canterbury.libguides.com/rights/thesesen
dc.titleNotes on the parallel decomposition theory of finite state machinesen
dc.typeTheses / Dissertations
thesis.degree.grantorUniversity of Canterburyen
thesis.degree.levelMastersen
thesis.degree.nameMaster of Scienceen
uc.collegeFaculty of Engineeringen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
mason_thesis.pdf
Size:
5.09 MB
Format:
Adobe Portable Document Format