It is well known [1, 3, 5] that the following concepts are closely related:
This thesis deals with a subfamily of sequential circuits corresponding to the following equivalent concepts:
Feedback-free cascades of set-reset flip-flops constitute an interesting subfamily of the family of sequential circuits. Those circuits show a high degree of modularity and regularity of structure. The flow of signals, whether they be Input, output, interconnection or clock signals, can all be made to flow in the same direction. It has been shown [4, 8] that feedback-free cascades of set-reset flip-flops, permutation-free automata, star-free regular events and group-free monoids are equivalent concepts.
This thesis presents the concept of a refined ordered successor set and a tree structure of such sets to give a new definition of permutation-free automata. Further, a simple test for the star-free property is given using the tree structure. The main goal of this thesis is to present, for any star-free event, a simple method for realizing the event by a feedback-free cascade of set-reset flip-flops using the tree structure to produce first a set of preserved covers for the automaton and then the interconnections between the flip-flops. It is assumed that the reader has some familiarity with automata theory and algebra.
In Chapter II the basic concepts of star-free, non-counting, and group-free events are given. In the course of this, automata and monoids are defined, and some of the interrelationships between different classes of events are shown. In preparation for the following chapter the definition of an ordered successor set is given.
In Chapter III a refined ordered successor set (ross) and a refined ordered successor set tree are defined, leading up to permutation-free events and to a demonstration of the equivalence of all the subclasses of regular events presented. The chapter closes with a test for star-free events.
Chapter IV contains two algorithms, one for the determination of a set of preserved covers of an automaton using the ross tree, and the other for the construction of the feedback-free cascade of set-reset flip-flops, using the ross tree and the covers obtained by the previous algorithm. The algorithms are based on the Krohn-Rhodes-Zeiger [9, 10] methods as presented by A. Ginzburg [12]. The main modification is the use of the ross tree.
In the Appendices, some of the work auxiliary to the thesis is presented: some star-free identities and a program to find the reduced state table of an automaton given the regular event it realizes.
