On the invertibility of finite state machines
R. R. Olson · NASA STI Repository (National Aeronautics and Space Administration) · 1970
The invertibility of finite state machines is considered in detail.Necessary and sufficient conditions for the general class, a s well as some important subclasses, of finite state machines to be invertible with delay L (called INV #L if L is the least delay for which an inverse exists) a r e given.Some structural properties of INV #L strongly connected machines with input and output sets of common order are derived.It is shown that every state on such a machine allows the same number of output sequences of length L or longer.Furthermore, it is shown that every set of final states, reachable from some known initial state with common output sequence of length L o r longer, has identical cardinality .The results of some previous research are related to this work.The concepts of information losslessness (IL) and information losslessness of finite order as established by Huffman a r e considered and related to invertibility.A necessary and sufficient condition for information losslessness in the case of strongly connected machines with equal order input and output sets is given.A new type of state equivalence is presented, viz, output equivalence.It is shown that the output equivalence relation has some particularly interest consequences in the casee of INV #L and IL machines.A state re I W #L machines based on output equivalence preserves invertibility, although not necessarily inverse delay.Although state reduced PL machines do not, in general, retain the IL property, it is shown that losslessness is preserved for the class of strongly connected machines.Several other structure preserving properties inherent in the state reduction of output equivalent states are demonstrated.Invertibility and losslessness of the class of finite input memory machines is considered.The implications of INV #L and IL characteristics on the output function which defines output response are investigated.for output functions of non-degenerate finite input memory machines to yield INV #L and IL behavior are given. Sufficient conditionsFinite output memory machines and properties related to invertibility a r e examined.It is concluded that a non-degenerate finite output memory machine is invertible with zero delay o r is not invertible with any delay.A particular problem concerning the invertibility of linear finite state machines is defined and solved.The result is a necessaryand sufficient con: dition for the existence of a feedforward inverse for a general linear finite state machine, thereby extending an earlier result of Massey and Sain.procedure for the construction of feedforward inverses with minimal delay for linear finite state machines is also given.A Upper bounds on inverse delay for an N state machine are investigated.It is shown for a certain restricted class of binary finite state machines th upper bound on inverse delay grows only linearly with N. ;s d s o shown that there exists an N state, INV #L machine with L = N(N-1)/2 for every N.The construction, however, requires a very large out large values of N.