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

### Keywords:

semi-topologies; closure operators; topological closures; Kleene closures of languages; unions; intersections; transitive closures of non-binary relations; difunctional closures of binary relations### Citations:

Zbl 0309.04002
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.