Compressed Structures for Partial Derivative Automata Constructions

The partial derivative automaton ([Formula: see text]) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton ([Formula: see text]), the algorithms that build [Formula: see text] in quadratic worst-case time first compute [Formula: see text]. Asymptotically, and on average for the uniform distribution, the size of [Formula: see text] is half the size of [Formula: see text], being both linear on the size of the expression. We address the construction of [Formula: see text] efficiently, on average, avoiding the computation of [Formula: see text]. The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building [Formula: see text]s from expressions in strong star normal form of size [Formula: see text] that runs, on average, in time that asymptotically behaves as [Formula: see text], and space as [Formula: see text]. Empirical results corroborate its good practical performance.