ML Anthology

The Complexity of Learning SUBSEQ (a)

Stephen A. Fenner, William I. Gasarch
ALT 2006 pp. 109-123
doi:10.1007/11894841_12 /alt/2006/fenner2006alt-complexity/

Abstract

Higman showed that if A is any language then SUBSEQ( A ) is regular, where SUBSEQ( A ) is the language of all subsequences of strings in A . We consider the following inductive inference problem: given A ( ε ), A (0), A (1), A (00), ... learn, in the limit, a DFA for SUBSEQ( A ). We consider this model of learning and the variants of it that are usually studied in inductive inference: anomalies, mindchanges, and teams.

PDF ALT Semantic Scholar

Cite

Text

Fenner and Gasarch. "The Complexity of Learning SUBSEQ (a)." International Conference on Algorithmic Learning Theory, 2006. doi:10.1007/11894841_12

Markdown

[Fenner and Gasarch. "The Complexity of Learning SUBSEQ (a)." International Conference on Algorithmic Learning Theory, 2006.](https://mlanthology.org/alt/2006/fenner2006alt-complexity/) doi:10.1007/11894841_12

BibTeX

@inproceedings{fenner2006alt-complexity,
  title     = {{The Complexity of Learning SUBSEQ (a)}},
  author    = {Fenner, Stephen A. and Gasarch, William I.},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2006},
  pages     = {109-123},
  doi       = {10.1007/11894841_12},
  url       = {https://mlanthology.org/alt/2006/fenner2006alt-complexity/}
}