On the Average State Complexity of Shuffle Ideals

Abstract

We consider shuffle ideals and their finite bases, both represented by regular expressions. We introduce an operation that, given a regular expression REfin representing a finite language, returns an expression for the shuffle ideal The expression L of alpha multiplied by the sum of capital sigma transposed represents a mathematical formula where L is a function of the small Greek letter alpha, and this result is multiplied by the transpose of the capital Greek letter sigma. This formula likely relates to a calculation involving these variables, emphasizing the relationship between the function L at alpha and the transposed sigma matrix or vector. This operation induces a new combinatorial class, which we call RESI. For both classes, we define the Antimirov automaton and provide results on their state complexity in the worst as well as the average case. For REfin, in the worst case, the number of states is at most ||, the number of letters in . The asymptotic average is, however, bounded by ||2. For RESI, in the worst case, the number of states is at most ||, the number of occurrences of in . On the other hand, the asymptotic average number of states is bounded by ||2. (c) IFIP International Federation for Information Processing 2027.