ML Anthology

A Note on the Query Complexity of Learning DFA (Extended Abstract)

José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
ALT 1992 pp. 53-62
doi:10.1007/3-540-57369-0_27 /alt/1992/balcazar1992alt-note/

Abstract

It is known [1] that the class of deterministic finite automata is polynomial time learnable by using membership and equivalence queries. We investigate — the query complexity — the number of membership and equivalence queries for learning deterministic finite automata. We first show two lower bounds in two different learning situations. Then we investigate the query complexity in general setting, and show some trade-off phenomenon between the number of membership and equivalence queries.

PDF ALT Semantic Scholar

Cite

Text

Balcázar et al. "A Note on the Query Complexity of Learning DFA (Extended Abstract)." International Conference on Algorithmic Learning Theory, 1992. doi:10.1007/3-540-57369-0_27

Markdown

[Balcázar et al. "A Note on the Query Complexity of Learning DFA (Extended Abstract)." International Conference on Algorithmic Learning Theory, 1992.](https://mlanthology.org/alt/1992/balcazar1992alt-note/) doi:10.1007/3-540-57369-0_27

BibTeX

@inproceedings{balcazar1992alt-note,
  title     = {{A Note on the Query Complexity of Learning DFA (Extended Abstract)}},
  author    = {Balcázar, José L. and Díaz, Josep and Gavaldà, Ricard and Watanabe, Osamu},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1992},
  pages     = {53-62},
  doi       = {10.1007/3-540-57369-0_27},
  url       = {https://mlanthology.org/alt/1992/balcazar1992alt-note/}
}