Random DFA's Can Be Approximately Learned from Sparse Uniform Examples

Lang, Kevin J.

doi:10.1145/130385.130390

Random DFA's Can Be Approximately Learned from Sparse Uniform Examples

Kevin J. Lang

COLT 1992 pp. 45-52

doi:10.1145/130385.130390 /colt/1992/lang1992colt-random/

Abstract

Approximate inference of finite state machines from sparse labeled examples has been proved NP-hard when an adversary chooses the target machine and the training set [Ang78, KV89, PW89]. We have, however, empirically found that DFA's are approximately learnable from sparse data when the target machine and training set are selected at random.

PDF COLT Semantic Scholar

Cite

Text

Lang. "Random DFA's Can Be Approximately Learned from Sparse Uniform Examples." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130390

Markdown

[Lang. "Random DFA's Can Be Approximately Learned from Sparse Uniform Examples." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/lang1992colt-random/) doi:10.1145/130385.130390

BibTeX

@inproceedings{lang1992colt-random,
  title     = {{Random DFA's Can Be Approximately Learned from Sparse Uniform Examples}},
  author    = {Lang, Kevin J.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1992},
  pages     = {45-52},
  doi       = {10.1145/130385.130390},
  url       = {https://mlanthology.org/colt/1992/lang1992colt-random/}
}