Sylvie Davies, Department of Pure Mathematics, University of Waterloo
"Algebraic Approaches to State Complexity of Regular Operations"
The state complexity of operations on regular languages is an active area of research in theoretical computer science. We describe various algebraic techniques for attacking state complexity problems. Our central result is a general method for constructing witness languages for operations - languages which attain the worst-case state complexity when used as the argument(s) of the operation. When a witness for an operation is known, determining the state complexity becomes essentially a combinatorial counting problem. We then look at methods to simplify the solution of these counting problems by taking advantage of the connections between regular languages and finite monoids.
MC 2009