R.: Symmetric groups and quotient complexity of boolean operations

Abstract. The quotient complexity of a regular language L is the num-ber of left quotients of L, which is the same as the state complexity of L. Suppose that L and L ′ are binary regular languages with quotient complexities m and n, and that the subgroups of permutations in the transition semigroups of the minimal deterministic automata accepting L and L ′ are the symmetric groups Sm and Sn of degrees m and n, respectively. Denote by ◦ any binary boolean operation that is not a constant and not a function of one argument only. For m,n ≥ 2 with (m,n) ∈ {(2, 2), (3, 4), (4, 3), (4, 4)} we prove that the quotient complex-ity of L ◦ L ′ is mn if and only either (a) m = n or (b) m = n and the bases (ordered pairs of generators) of Sm and Sn are not conjugate. For (m,n) ∈ {(2, 2), (3, 4), (4, 3), (4, 4)} we give examples to show that this need not hold. In proving these results we generalize the notion of uniform minimality to direct products of automata. We also establish a non-trivial connection between complexity of boolean operations and group theory