Equivalence problem of non-deterministic finite automata

摘要

Here considered is the bound to the lengths of input strings to be examined for checking equivalence of non-deterministic automata. It is shown that the optimal bound is of order O(2m + 2n), where m and n are the state numbers of the automata under question. For one-input automata, the lengths of strings to be examined can be considerably reduced, but they are not bounded by any polynomial function of state numbers.