ML Anthology

Learning Regular Sets with an Incomplete Membership Oracle

Nader H. Bshouty, Avi Owshanko
COLT 2001 pp. 574-588
doi:10.1007/3-540-44581-1_38 /colt/2001/bshouty2001colt-learning-a/

Abstract

This paper gives an “efficient” algorithm for learning deterministic finite automata by using an equivalence oracle and an incomplete membership oracle. This solves an open problem that was posed by Angluin and Slonim in 94.

PDF COLT Semantic Scholar

Cite

Text

Bshouty and Owshanko. "Learning Regular Sets with an Incomplete Membership Oracle." Annual Conference on Computational Learning Theory, 2001. doi:10.1007/3-540-44581-1_38

Markdown

[Bshouty and Owshanko. "Learning Regular Sets with an Incomplete Membership Oracle." Annual Conference on Computational Learning Theory, 2001.](https://mlanthology.org/colt/2001/bshouty2001colt-learning-a/) doi:10.1007/3-540-44581-1_38

BibTeX

@inproceedings{bshouty2001colt-learning-a,
  title     = {{Learning Regular Sets with an Incomplete Membership Oracle}},
  author    = {Bshouty, Nader H. and Owshanko, Avi},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2001},
  pages     = {574-588},
  doi       = {10.1007/3-540-44581-1_38},
  url       = {https://mlanthology.org/colt/2001/bshouty2001colt-learning-a/}
}