Regular Expression Length via Arithmetic Formula Complexity

摘要

We prove lower bounds on the length of regular expressions for finite languages by methods from arithmetic circuit complexity. First, we show a reduction from expression length to monotone arithmetic formula size. This yields lower bounds of nk~(Ω(log k)) for the binomial language of all words with exactly k ones and n - k zeros, and of n~(Ω(log n)) for the language of all Dyck words of length 2n. We also determine the blow-up of expression length when applying the operations intersection or shuffle to finite languages. Second, we adapt a lower bound method for multilinear arithmetic formulas by Hrubes and Yehudayoff to regular expressions. With this method we give a tight lower bound of Ω(n~(-1) p~(log(n/log p)-2)) for the language of all binary numbers with n bits that are divisible by a given odd integer p.