Algebraic Approaches to State Complexity of Regular Operations

Abstract

The state complexity of operations on regular languages is an active area of research in theoretical computer science. Through connections with algebra, particularly the theory of semigroups and monoids, many problems in this area can be simplified or completely reduced to combinatorial problems. We describe various algebraic techniques for attacking state complexity problems. We present a general method for constructing witness languages for operations -- languages that attain the worst-case state complexity when used as the argument(s) of the operation. Our construction is based on full transformation monoids, which contain all functions from a finite set into itself. When a witness for an operation is known, determining the state complexity essentially becomes a counting problem. These counting problems, however, are not necessarily easy, and the witness languages produced by this method are not ideal in the sense that they have extremely large alphabets. We thus investigate some commonly used operations in detail, and look for algebraic techniques to simplify the combinatorial side of state complexity problems and to simplify the search for small-alphabet witnesses. For boolean operations (e.g., union, intersection, difference) we show that these combinatorial problems can be solved easily in special cases by studying the subgroup of permutations in the syntactic monoid of a witness candidate. If the subgroup of permutations is known to have some strong transitivity property, such as primitivity or 2-transitivity, we can draw conclusions about the worst-case state complexity when this language is used in a boolean operation. For the operations of concatenation and Kleene star (an iterated version of concatenation), we describe a “construction set” method to simplify state complexity lower-bound proofs, and determine some algebraic conditions under which this method can be applied. For the reversal operation, we show that the state complexity of the reverse of a language is closely related to the syntactic monoid of the language, and use this fact to investigate a generalized version of the reversal state complexity problem. After describing our techniques, we demonstrate them by applying them to some classical state complexity problems. We obtain complex generalizations of the classical results that would be difficult to prove without the machinery we develop.