REALIZATION OF STAR-FREE EVENTS

by

Eric Bierman, B. Eng.

A Thesis

Submitted to the Faculty of Graduate Studies through the Department of Electrical Engineering in Partial Fulfillment of the Requirements for the Degree of Master of Applied Science at the University of Waterloo

I hereby declare that I am the sole author of this thesis. I authorize the University of Waterloo to lend it to other institutions or individuals for the purpose of scholarly research.

© Eric Bierman, July, 1971

Table of Contents

Abstract
Acknowledgements
Chapter I - Introduction
Chapter II - Preliminaries
2.1 - Star-Free Regular Events
2.2 - Non-Counting Regular Events
2.3 - Automata and Monoids
2.4 - Group-Free Monoids, Automata and Events
Chapter III - Permutation-Free Events
3.1 - The Ross Tree
3.2 - Equivalence of Classes of Events
3.3 - Test for Star-Free Events
Chapter IV - Realization of Star-Free Events
4.1 - Covers
4.2 - The Cover Algorithm
4.3 - Reset Machines
4.4 - The Interconnection Algorithm
4.5 - Hardware Implementation
Chapter V - Conclusions
Appendix A
Appendix B
Bibliography
List of Figures

Valid XHTML 1.0! Valid CSS!