Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1979 | 10.1016/0022-0000(79)90048-5 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
non deterministic finite automata | Journal | 18 |
Issue | ISSN | Citations |
1 | 0022-0000 | 3 |
PageRank | References | Authors |
2.96 | 2 | 1 |