Symmetric groups and quotient complexity of Boolean operations
From MaRDI portal
Abstract: The quotient complexity of a regular language L is the number 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 transition semigroups of the minimal deterministic automata accepting L and L' are the symmetric groups S_m and S_n of degrees m and n, respectively. Denote by o any binary boolean operation that is not a constant and not a function of one argument only. For m,n >= 2 with (m,n) not in {(2,2),(3,4),(4,3),(4,4)} we prove that the quotient complexity of LoL' is mn if and only either (a) m is not equal to n or (b) m=n and the bases (ordered pairs of generators) of S_m and S_n are not conjugate. For (m,n)in {(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.
Recommendations
Cited in
(6)- Primitivity, uniform minimality, and state complexity of Boolean operations
- Complexity of suffix-free regular languages
- Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
- Unrestricted state complexity of binary operations on regular languages
- Bit complexity of breaking and achieving symmetry in chains and rings
- Most complex non-returning regular languages
This page was built for publication: Symmetric groups and quotient complexity of Boolean operations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167822)
