SPEAKER: Emilie Charlier
University of Waterloo
TITLE: Finite Orbits of Language Operations
We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. We also provide bounds, tight if possible, for the orbit size for each subset of the set of operations under consideration. This generalizes previous results about complement, Kleene closure, and positive closure.
This is joint work with Mike Domaratzki, Tero Harju and Jeffrey Shallit, and was presented at LATA 2011, last May.