State Complexity and the Monoid of Transformations of a Finite Set
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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
Added discussion of prior work. Generalized results to both even and odd cases. Corrected mistakes