VC-dimensions of nondeterministic finite automata for words of equal length
This work addresses theoretical computer science problems in automata theory and learning theory, offering incremental improvements to known bounds.
The paper tackles the problem of bounding the VC dimension of languages accepted by nondeterministic finite automata (NFAs) on words of equal length, providing a quadratic lower bound in terms of the number of states, and strengthens existing upper bounds on nondeterministic state complexity for finite languages.
Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$. We give a quadratic lower bound on the VC dimension of \[ NFA_2(q)\cap B_n = \{L\cap B_n \mid L \in NFA_2(q)\} \] as a function of $q$. Next, the work of Gruber and Holzer (2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in $B_n$, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on $n$ of the VC dimension and testing dimension of $NFA_2(q)\cap B_n$.