State Complexity and the Monoid of Transformations of a Finite Set

Abstract

In this paper we consider the state complexity of an operation on formal languages, root(L). This naturally entails the discussion of the monoid of transformations of a finite set. We obtain good upper and lower bounds on the state complexity of root(L) over alphabets of all sizes.

Added discussion of prior work. Generalized results to both even and odd cases. Corrected mistakes