×

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

Diekert, Volker (ed.) et al., Developments in language theory. 13th international conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02736-9/pbk). Lecture Notes in Computer Science 5583, 125-144 (2009).
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 closure is either Kleene closure or positive closure. We classify languages according to the structure of the algebra 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.
For the entire collection see [Zbl 1165.68006].

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974) · Zbl 0326.68005
[2] Brzozowski, J., Grant, E., Shallit, J.: Closures in formal languages and Kuratowski’s theorem (preprint) (January 2009), http://arxiv.org/abs/0901.3761 · Zbl 1246.68139
[3] Brzozowski, J., Grant, E., Shallit, J.: Closures in formal languages: concatenation, separation, and algorithms (January 2009), http://arxiv.org/abs/0901.3763 · Zbl 1246.68139
[4] Burris, S.N., Sankappanavar, H.P.: A Course in Universal Algebra, 2nd edn., http://www.math.uwaterloo.ca/snburris/htdocs/ualg.html · Zbl 0478.08001
[5] Chagrov, A.V.: Kuratowski numbers. In: Application of Functional Analysis in Approximation Theory, Kalinin. Gos. Univ., Kalinin, pp. 186–190 (1982) (in Russian)
[6] Ellul, K., Krawetz, B., Shallit, J., Wang, M.-w.: Regular expressions: new results and open problems. J. Autom. Lang. Combin. 10, 407–437 (2005) · Zbl 1143.68434
[7] Fife, J.H.: The Kuratowski closure-complement problem. Math. Mag. 64, 180–182 (1991) · Zbl 0735.54001
[8] Gardner, B.J., Jackson, M.: The Kuratowski closure-complement theorem. New Zealand J. Math. (to appear); Preprint available at http://www.latrobe.edu.au/mathstats/department/algebra-research-group/Papers/GJ_Kuratowski.pdf · Zbl 1185.54002
[9] Graham, R.L., Knuth, D.E., Motzkin, T.S.: Complements and transitive closures. Discrete Math. 2, 17–29 (1972) · Zbl 0309.04002
[10] Hammer, P.C.: Kuratowski’s closure theorem. Nieuw Archief v. Wiskunde 7, 74–80 (1960) · Zbl 0137.15503
[11] Kuratowski, C.: Sur l’opération \(\overline{A}\) de l’analysis situs. Fund. Math. 3, 182–199 (1922) · JFM 48.0210.04
[12] Lyndon, R.C., Schützenberger, M.P.: The equation aM = bN cP in a free group. Michigan Math. J. 9, 289–298 (1962) · Zbl 0106.02204
[13] 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.