Finite Orbits of Language Operations



: Charlier E, Domaratzki M, Harju T, Shallit J

: Dediu Adrian-Horja, Inenaga Shunsuke, Martin-Vide Carlos

: 2011

: Lecture Notes in Computer Science

: Language and Automata Theory and Applications

: LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS

: LECT NOTES COMPUT SC

: 6638

: 204

: 215

: 2

: 978-3-642-21253-6

: 0302-9743

: https://research.utu.fi/converis/portal/Publication/2874876


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. This generalizes previous results about complement, Kleene closure, and positive closure.

Last updated on 2024-26-11 at 11:23