ML Anthology

The VC-Dimensions of Finite Automata with N States

Yoshiyasu Ishigami, Sei'ichi Tani
ALT 1993 pp. 328-341
doi:10.1007/3-540-57370-4_58 /alt/1993/ishigami1993alt-vcdimensions/

Abstract

In this paper, we investigate the VC-dimensions of finite automata. We show that for a fixed positive integer k (1) the VC-dimension of DFA_k, n, which is the class of dfas of an alphabet size k whose minimum states dfa has at most n states, is ( k − 1+ o (1)) n log n , (2) the VC-dimension of NFA_k, n, which is the class of nfas of an alphabet size k whose minimum states nfa has at most n states, is Q(n ^2) and (3) the VC-dimension of CDFA_k, n, which is the class of commutative dfas of an alphabet size k whose minimum states commutative dfas has at most n states, is (1+o(1)) n . These results are applied to the problems in computational learning theory.

PDF ALT Semantic Scholar

Cite

Text

Ishigami and Tani. "The VC-Dimensions of Finite Automata with N States." International Conference on Algorithmic Learning Theory, 1993. doi:10.1007/3-540-57370-4_58

Markdown

[Ishigami and Tani. "The VC-Dimensions of Finite Automata with N States." International Conference on Algorithmic Learning Theory, 1993.](https://mlanthology.org/alt/1993/ishigami1993alt-vcdimensions/) doi:10.1007/3-540-57370-4_58

BibTeX

@inproceedings{ishigami1993alt-vcdimensions,
  title     = {{The VC-Dimensions of Finite Automata with N States}},
  author    = {Ishigami, Yoshiyasu and Tani, Sei'ichi},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {1993},
  pages     = {328-341},
  doi       = {10.1007/3-540-57370-4_58},
  url       = {https://mlanthology.org/alt/1993/ishigami1993alt-vcdimensions/}
}