论文标题
不确定性有限自动机的VC维度相等的单词
VC-dimensions of nondeterministic finite automata for words of equal length
论文作者
论文摘要
令$ nfa_b（q）$表示非确定性有限自动机接受的一组语言，$ q $状态在带有$ b $字母的字母上。令$ b_n $表示长度$ n $的单词。我们在\ [ nfa_2（q）\ cap b_n = \ {l \ cap b_n \ mid l \ in nfa_2（q）\} \]作为$ q $的函数。 接下来，Gruber和Holzer（2007）的工作为$ b_n $中包含的有限语言的不确定性状态复杂性提供了上限，我们使用方法来加强。 最后，我们对$ nfa_2（q）\ cap b_n $的$ n $的依赖性给出了一些理论和实验结果。
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$.
