Measuring average complexity of automata operations

The worst-case complexity of the conversions between different representations of regular languages is well studied. However, for practical purposes, the average-case complexity of such conversions is much more relevant than its worst-case complexity, which is often due to some particular and rarely occurring cases. Still, the average-case analysis is, in general, a difficult task. One approach is to consider uniform random generators and to perform statistically significant experiments. Another approach is the use of asymptotic methods.

In this presentation, we discuss asymptotic average-case results on the size of non-deterministic finite automata obtained from regular expressions, using the symbolic method and the framework of analytic combinatorics.