A generalized closure and complement phenomenon
type: Item
instance of: scholarly article
title: A generalized closure and complement phenomenon
zbMATH Open document ID: 0542.54001
DOI: 10.1016/0012-365X(84)90055-4
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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 \textit{C. Kuratowski} [Fundam. Math. 3, 182-199 (1922)] for topological closures (with 14 as a bound), and later by \textit{R. L. Graham}, \textit{D. E. Knuth} and \textit{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.
Mathematics Subject Classification ID: 54A05
Mathematics Subject Classification ID: 03E20
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3861977
zbMATH Keywords: semi-topologies
zbMATH Keywords: closure operators
zbMATH Keywords: topological closures
zbMATH Keywords: Kleene closures of languages
zbMATH Keywords: unions
zbMATH Keywords: intersections
zbMATH Keywords: transitive closures of non-binary relations
zbMATH Keywords: difunctional closures of binary relations
author: David Peleg
MaRDI profile type: Publication
cites work: Structure and complexity of relational queries
cites work: Complements and transitive closures
cites work: Languages that Capture Complexity Classes
description: scientific article; zbMATH DE number 3861977