A decision procedure for generalized sequential mapability-onto of regular sets
Robert McNaughton · 1971
In [1] various problems are solved about the possibility of mapping regular sets into or onto other regular sets by means of a complete sequential machine or a generalized sequential machine under various restraints. One problem in this class has remained open. That problem, as restated on pp. 129-130 of [2], is whether it is “recursively solvable to determine for arbitrary regular sets L1 and L2 whether there exists a generalized sequential machine S such that S(L1) = L2.” The claim is hereby made on the affirmative solution to this problem.