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

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.

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
Full Text:
DOI

### 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 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.