The unsolvability of the equivalence problem for e-free NGSM's with unary input (output) alphabet and applications
Óscar H. Ibarra · 1977
It is shown that the equivalence problem is unsolvable for ε-free nondeterministic generalized sequential machines whose input/output are restricted to unary/binary (binary/unary) alphabets. This strengthens a known result of Griffiths. Applications to some decision problems concerning right-linear grammars and directed graphs are also given.