Realization with Feedback Encoding. II: Applications to Distinguishing Sequences
Dennis P. Geller · SIAM Journal on Computing · 1975
We continue the work of a previous paper by developing techniques for realizing (with feedback encoding) a given machine by one which admits a distinguishing sequence. We allow no expansion of state set or input set size, and attempt to minimize the number of additional outputs needed. With feedback encoding, this usually behavioral problem becomes one involving only (graph) structural properties of the given machine. In particular, we cast the problem of reducing the number of instances of sets of states merging under an input as one involving coloring a bipartite graph derived from the machine.