论文标题
正则表达长度通过算术公式复杂性
Regular expression length via arithmetic formula complexity
论文作者
论文摘要
通过算术电路复杂性的方法，我们证明了有限语言的正则表达式长度的下限。首先，我们显示一个减少：语言的正则表达式的长度$ l \ subseteq \ {0,1 \}^n $从下面的最小尺寸限制在单调算术公式的最小尺寸上，该公式计算具有$ l $的多项式，该多项式具有$ l $，它将其作为expentors vectors seet vectors vectors veectors作为vectors。此结果可为所有单词的二项式语言提供较低的界限，这些单词恰好是$ k $，$ n-k $ zeros以及所有长度为$ 2n $的dyck单词的语言。我们还确定了有限语言的正则表达式语言操作（交叉和随机散发）的爆炸。其次，我们通过所谓的对数产物多项式的多线性算术公式适应了一种下界方法，以适应正则表达式。通过这种方法，我们显示了所有二进制数字的语言几乎紧密的下限，这些语言的$ n $位可以由给定的奇数整数$ p $排除，用于$ k $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $的语言。
We prove lower bounds on the length of regular expressions for finite languages by methods from arithmetic circuit complexity. First, we show a reduction: the length of a regular expression for a language $L\subseteq \{0,1\}^n$ is bounded from below by the minimum size of a monotone arithmetic formula computing a polynomial that has $L$ as its set of exponent vectors, viewing words as vectors. This result yields lower bounds for the binomial language of all words with exactly $k$ ones and $n-k$ zeros and for the language of all Dyck words of length $2n$. We also determine the blow-up of language operations (intersection and shuffle) of regular expressions for finite languages. Second, we adapt a lower bound method for multilinear arithmetic formulas by so-called log-product polynomials to regular expressions. With this method we show almost tight lower bounds for the language of all binary numbers with $n$ bits that are divisible by a given odd integer $p$, for the language of all words of length $n$ over a $k$ letter alphabet with an even number of occurrences of each letter and for the language of all permutations of $\{1,\dots, n\}$.
