Output completeness in sequential machines
Gene F. Rose · Proceedings of the American Mathematical Society · 1962
In §5 oí [l], Ginsburg considers states of complete sequential machines that yield all possible output words, calling them "output complete states."1For any state that is not output complete, there is a shortest word not yielded by it, and Ginsburg points out that, among all machines in n states, r inputs and m outputs, these shortest words have a least upper bound k(m, n, r) depending only upon m, n and r.The question of explicitly expressing k(m, », r) or an upper bound for it was left open.It follows as a special case of the present Theorem 2.4 that 2n_1 is an upper bound.Moreover, by Corollary 3.3, for all sufficiently large m and r, 2n_1 is the least upper bound.An immediate implication of the primitive recursiveness of this bound is that the decision problem for output completeness is solvable.The results for individual states were obtained as a special case of analogous findings for sets of states.