@article{Angluin:ML:1990,
    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.},
    Address = {USA},
    Author = {Angluin, Dana},
    File = {Negative Results for Equivalence Queries - angluin1990 - a.pdf},
    ISSN = {0885-6125},
    Journal = {Mach. Learn.},
    Keywords = {Concept learning, queries},
    Month = {jul},
    Number = {2},
    Pages = {121--150},
    Publisher = {Kluwer Academic Publishers},
    Title = {Negative Results for Equivalence Queries},
    URL = {https://doi.org/10.1023/A:1022692615781},
    Volume = {5},
    Year = {1990},
    bdsk-url-1 = {https://doi.org/10.1023/A:1022692615781},
    date-added = {2023-10-05 08:05:15 +0200},
    date-modified = {2023-10-05 08:06:40 +0200},
    issue_date = {Jun. 1990},
    numpages = {30},
    doi = {10.1023/A:1022692615781}
}

@article{Angluin:ML:1990, 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.}, Address = {USA}, Author = {Angluin, Dana}, File = {Negative Results for Equivalence Queries - angluin1990 - a.pdf}, ISSN = {0885-6125}, Journal = {Mach. Learn.}, Keywords = {Concept learning, queries}, Month = {jul}, Number = {2}, Pages = {121--150}, Publisher = {Kluwer Academic Publishers}, Title = {Negative Results for Equivalence Queries}, URL = {https://doi.org/10.1023/A:1022692615781}, Volume = {5}, Year = {1990}, bdsk-url-1 = {https://doi.org/10.1023/A:1022692615781}, date-added = {2023-10-05 08:05:15 +0200}, date-modified = {2023-10-05 08:06:40 +0200}, issue_date = {Jun. 1990}, numpages = {30}, doi = {10.1023/A:1022692615781} }