Sylvie
Davies,
Department
of
Pure
Mathematics
University
of
Waterloo
The state complexity of a regular language is the minimal number of states needed to recognize that language with a DFA. Then given a unary operation on regular languages, we may ask: if the input language is recognized by a DFA with n states, what is the worst-case state complexity of the output language, as a function of n? This worst-case value is called the state complexity of the operation. For the square operation (concatenation of a language with itself), the state complexity is known if the input is an arbitrary regular language, but not if the input is a star-free language. The state complexity of many common operations on star-free languages (union, intersection, concatenation, star, reversal) is known, but square remains elusive. We describe recent progress on this still-open problem, building on some work of Brzozowski and Szykuła on large aperiodic semigroups.