1. Composition and orbits of language operations: finiteness and upper bounds.
- Author
-
Charlier, Émilie, Domaratzki, Mike, Harju, Tero, and Shallit, Jeffrey
- Subjects
MATHEMATICAL bounds ,FORMAL languages ,COMPOSITION (Language arts) ,SUFFIXES & prefixes (Grammar) ,MATHEMATICAL proofs ,NUMBER theory ,MONOIDS ,EQUIVALENCE classes (Set theory) - Abstract
We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. Ifxandyare compositions, we sayxis equivalent toyif they have the same effect on all languagesL. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any languageLunder the elements of the monoid is finite and bounded, independent ofL. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF