Compressed Structures for Partial Derivative Automata Constructions

The partial derivative automaton (A(PD)) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton (A(POS)), the algorithms that build A(PD) in quadratic worst-case time first compute A(POS). Asymptotically, and on average for the uniform distribution, the size of A(PD) is half the size of A(POS), being both linear on the size of the expression. We address the construction of A(PD) efficiently, on average, avoiding the computation of A(P...

Average State Complexity of Partial Derivative Automata for Synchronised Shuffles

Synchronised shuffle operators allow to specify symbols on which the operands must or can synchronise instead of interleave. Recently, partial derivative and position based automata for regular expressions with synchronised shuffle operators were introduced. In this paper, using the framework of analytic combinatorics, we study the asymptotic average state complexity of partial derivative automata for regular expressions with strongly and arbitrarily synchronised shuffles. The new results ext...

Regular Expressions Avoiding Absorbing Patterns and the Significance of Uniform Distribution

Although regular expressions do not correspond univocally to regular languages, it is still worthwhile to study their properties and algorithms. For the average case analysis one often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward ...

Language Quotients Revisited

We revisit the basic concept of quotient of a regular language R by a language L that is not necessarily regular. We revise the deterministic complexity upper bounds of the quotient operation, and we also address the nondeterministic case. Specifically, the revised deterministic upper bound is shown to be more accurate for all hard streams of regular languages. When both languages R and L are regular, we give algorithms to construct their quotient in four ways. If the two languages are given ...