Closures in formal languages and Kuratowski’s theorem. (English) Zbl 1246.68139

Summary: A famous theorem of Kuratowski states that, in a topological space, at most 14 distinct sets can be produced by repeatedly applying the operations of closure and complement to a given set. We re-examine this theorem in the setting of formal languages, where by “closure” we mean either Kleene closure or positive closure. We classify languages according to the structure of the algebras they generate under iterations of complement and closure. There are precisely 9 such algebras in the case of positive closure, and 12 in the case of Kleene closure. We study how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the separation axioms in topological spaces; one of our main results is that there is a clopen partition separating two words if and only if the words do not commute. We can decide in quadratic time if the language specified by a DFA is closed, but if the language is specified by an NFA, the problem is PSPACE-complete.


68Q45 Formal languages and automata
54A05 Topological spaces and generalizations (closure spaces, etc.)
68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Aho A., The Design and Analysis of Computer Algorithms (1974) · Zbl 0326.68005
[2] A. V. Chagrov, Application of Functional Analysis in Approximation Theory (Kalinin. Gos. Univ., Kalinin, 1982) pp. 186–190.
[3] Ellul K., J. Autom. Lang. Combin. 10 pp 407–
[4] DOI: 10.2307/2691300 · Zbl 0735.54001 · doi:10.2307/2691300
[5] Gardner B. J., New Zealand J. Math. 38 pp 9–
[6] DOI: 10.1016/0012-365X(72)90057-X · Zbl 0309.04002 · doi:10.1016/0012-365X(72)90057-X
[7] Hammer P. C., Nieuw Archief v. Wiskunde 7 pp 74–
[8] Kuratowski C., Fund. Math. 3 pp 182–
[9] Lyndon R. C., Michigan Math. J. 9 pp 289–
[10] DOI: 10.1016/0012-365X(84)90055-4 · Zbl 0542.54001 · doi:10.1016/0012-365X(84)90055-4
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.