The unsolvability of the equivalence problem for e-free NGSM´s with unary input (output) alphabet and applications

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.