STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
Bryan Krawetz, John Lawrence, Jeffrey O. Shallit · International Journal of Foundations of Computer Science · 2005
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. As well, we present an application of these results to the problem of 2DFA-DFA conversion.