On the orbit of closure-involution operations – the case of formal languages. (English) Zbl 1439.68013

Dassow, Jürgen

Theor. Comput. Sci. 777, 192-203 (2019).

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.

Reviewer: Andreas Maletti (Leipzig)

MSC:

68Q45

Formal languages and automata

Keywords:

orbit of languages; complement; reversal; involution; closure operator; Kuratowski’s closure-complement theorem; Kleene closure; prefix closure; suffix closure; infix closure

References:

[1]	Brzozowski, J.; Grant, E.; Shallit, J., Closures in formal languages and Kuratowski’s theorem, (Diekert, V.; Nowotka, D., Development of Languages 2009. Development of Languages 2009, LNCS, vol. 5583 (2009)), 125-144 · Zbl 1247.68129
[2]	Charlier, É.; Domaratzki, M.; Harju, T.; Shallit, J., Finite orbits of language operations, (Dediu, A.-H.; Inenaga, Sh.; Martin-Vide, C., Languages and Automata, Theory and Application 2011. Languages and Automata, Theory and Application 2011, LNCS, vol. 6638 (2011)), 204-215 · Zbl 1260.68197
[3]	Gardner, B. J.; Jackson, M., The Kuratowski closure-complement theorem, New Zealand J. Math., 38, 9-44 (2008) · Zbl 1185.54002
[4]	Hammer, D. H., Kuratowski’s closure theorem, Nieuw Arch. Wiskd., 7, 74-80 (1960) · Zbl 0137.15503
[5]	Kuratowski, C., Sur l’opération \(\overline{A}\) de l’analysis situs, Fund. Math., 3, 182-199 (1922) · JFM 48.0210.04
[6]	Peleg, D., A generalized closure and complement phenomenon, Discrete Math., 50, 285-293 (1984) · Zbl 0542.54001