VC-dimensions of finite automata and commutative finite automata with k letters and n states

✍ Scribed by Yoshiyasu Ishigami; Sei'ichi Tani

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 723 KB
• Volume: 74
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00050-9

✦ Synopsis

An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k ( > 2), that (1) the VC-dimension of DFAk(n) := {L c{1,2,...,k}* : some deterministic finite automaton with at most n states accepts L} is n + log, n -O(log log n) for k = 1 and (k -1 + o( 1 ))n log, n for k > 2, and (2) the VC-dimension of CDFAk(n) := {L E DFAk(n) : L is commutative} is n + o(n).