ML Anthology

Equivalence Queries and Approximate Fingerprints

Dana Angluin
COLT 1989 pp. 134-145
doi:10.1016/B978-0-08-094829-4.50012-X /colt/1989/angluin1989colt-equivalence/

Abstract

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.

COLT Semantic Scholar

Cite

Text

Angluin. "Equivalence Queries and Approximate Fingerprints." Annual Conference on Computational Learning Theory, 1989. doi:10.1016/B978-0-08-094829-4.50012-X

Markdown

[Angluin. "Equivalence Queries and Approximate Fingerprints." Annual Conference on Computational Learning Theory, 1989.](https://mlanthology.org/colt/1989/angluin1989colt-equivalence/) doi:10.1016/B978-0-08-094829-4.50012-X

BibTeX

@inproceedings{angluin1989colt-equivalence,
  title     = {{Equivalence Queries and Approximate Fingerprints}},
  author    = {Angluin, Dana},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1989},
  pages     = {134-145},
  doi       = {10.1016/B978-0-08-094829-4.50012-X},
  url       = {https://mlanthology.org/colt/1989/angluin1989colt-equivalence/}
}