Negative Results for Equivalence Queries

Abstract

We consider the problem of exact identification of classes of concepts using only equivalence queries. We define a combinatorial property, approximate fingerprints , of classes of concepts and show that no class with this property can be exactly identified in polynomial time using only equivalence queries. As applications of this general theorem, we show that there is no polynomial time algorithm using only equivalence queries that exactly identifies deterministic or nondeterministic finite state acceptors, context free grammars, or disjunctive or conjunctive normal form boolean formulas.