Automata for Synchronised Shuffle on Backbones

Abstract

Considering regular expressions extended with synchronised shuffle on backbones, we present two equivalent automata: the location based position automaton and the partial derivative automaton. We show that the latter is a quotient of the former. Using the framework of analytic combinatorics, we study the average complexity of the partial derivative automaton. Surprisingly, for binary and ternary alphabets the average number of partial derivatives by a symbol is exponential on the size of the expression, while it is constant for larger alphabets which is what happens with the results for all other regular operators studied so far. Furthermore, we prove that the average number of states of the partial derivative automaton is bounded from above by (1.57708 + o(1))(m), while in the worst-case that value is O(3(m)), where m is the alphabetic size of the expression.