Regular expression length via arithmetic formula complexity

Ehud Cseresnyes, Hannes Seiwert

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 e…