by
This thesis presents an algorithm for determining whether or not a regular event is also a star-free event. From the state table of the automaton accepting the event, an ordered input successor tree is constructed in a well-defined manner with branches terminating when a node is reached which is identical to, or a permutation of a previous node in that branch. The event is star-free if none of the branches terminate with a permutation. A proof of the validity of the test is given, along with examples. Furthermore, the tree is used to find a set of progressively finer preserved covers, starting with the trivial cover of one block and proceeding until the trivial cover of all singletons is reached. The covers are written in a matrix form in such a way that the rows of the covers represent states of generalized set-reset flip-flops. Another algorithm, using the tree, gives the interconnections required between the flip-flops to yield a feedback-free realization of star-free events using only set-reset flip-flops and combinatorial logic. Proofs and examples are also given.
The author wishes to express his sincere gratitude to Professor Janusz A. Brzozowski for introducing the author to this topic and for his patient guidance and encouragement throughout this research.
The author wishes to thank Miss Carol Donkin for her careful typing of this thesis on a SCRIPT terminal.
The author also wishes to acknowledge the financial support of the Northern Electric Company Limited, the author's employer throughout this research.
