×

A generalized closure and complement phenomenon. (English) Zbl 0542.54001

The number of different sets that can be generated from a given set by applications of complement and closure operators is finite and small. This fact, stated originally by C. Kuratowski [Fundam. Math. 3, 182-199 (1922)] for topological closures (with 14 as a bound), and later by R. L. Graham, D. E. Knuth and T. S. Motzkin [Discrete Math. 2, 17-29 (1972; Zbl 0309.04002)] for transitive closures of binary relations (with 10 as a bound), is generalized to other closure operators, with different bounds. Several examples are given, including Kleene closures of languages, unions and intersections with a fixed set, transitive closures of non-binary relations and difunctional closures of binary relations.

MSC:

54A05 Topological spaces and generalizations (closure spaces, etc.)
03E20 Other classical set theory (including functions, relations, and set algebra)
68Q45 Formal languages and automata

Citations:

Zbl 0309.04002
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chandra, A.; Harel, D., Structure and complexity of relational queries, J. Comput. System. Sci., 25, 99-128 (1982), (also: CS82-05, Weizmann Institute of Science, Dept. of Applied Mathematics, Rehovot, Israel) · Zbl 0511.68073
[2] Graham, R. L.; Knuth, D. E.; Motzkin, T. S., Complements and transitive closures, Discrete Math., 2, 17-29 (1972) · Zbl 0309.04002
[3] Immerman, N., Languages which capture complexity classes, (15th ACM SIGACT Symposium (April 1983)) · Zbl 0634.68034
[4] Kuratowski, C., Sur l’operation Ā de l’analysis situs, Fund. Math., 3, 182-199 (1922)
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.