Equivalence queries and approximate fingerprints
Dana Angluin · Conference on Learning Theory · 1989
We report results showing that there is no polynomial time algorithm using only equivalence queries that exactly identifies deterministic finite state acceptors, nondeterministic finite state acceptors, context free grammars, disjunctive or conjunctive normal form boolean formulas, or μ -formulas.