On the orbit of closure-involution operations -- the case of formal languages (Q2422027)

The contribution discusses the number of languages achievable from a given language using a closure operation and an involution. A classical result by Kuratowski shows that at most 14 sets can be obtained from a given set using only a single closure operator together with complementation. For a given language class, e.g., the regular languages, the orbit of the two operations is the set of numbers achievable for all the languages in the language class. As closure operations the Kleene-closure, the prefix and suffix as well as the infix closure are considered. For example, given the language \(\Sigma^*\) and the operations Kleene-closure as well as complementation we obtain the four languages \(\Sigma^*\), \(\emptyset\), \(\{\varepsilon\}\), and \(\Sigma^+\). Additionally, for all closure operators and monotone involutions it is demonstrated that certain small numbers will certainly be contained in the orbit. More specifically, it shows that for those factor closures and complement exactly \(2\), \(4\), and \(6\) languages are derivable. It also characterizes the languages that achieve \(2\) and \(4\) derivable languages for those operations. A similar result presenting the exact orbit is also derived for the standard closure operators together with reversal, where also odd numbers can occur. The next section considers a special closure operator, for which infinitely many languages can be derived from a single language together with reversal. The last section shows that certain small numbers are in the orbit for each closure operator together with a monotone involution. Overall, the contribution is well written and very accessible. All notions are carefully defined and illustrated. Anyone with a minimal background in automata theory should be able to fully appreciate the material covered.