×

Generalized domination in closure systems. (English) Zbl 1093.68033

Summary: In the context of extracting maximal item sets and association rules from a binary database, the graph-theoretic notion of domination was recently used to characterize the neighborhood of a concept in the corresponding lattice.
In this paper, we show that the notion of domination can in fact be extended to any closure operator on a finite universe and be efficiently encoded into propositional Horn functions. This generalization enables us to endow notions and algorithms related to formal concept analysis with Horn minimization and minimal covers of functional dependencies in relational databases.

MSC:

68P15 Database theory
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68R10 Graph theory (including graph drawing) in computer science

Software:

Ltur
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Barbut, M.; Monjardet, B., Ordre et classification, (1970), Classiques Hachette · Zbl 0267.06001
[2] Bernard, J.-M.; Poitrenaud, S., L’analyse implicative bayésienne multivariée d’un questionnaire binaire: quasi-implications et treillis de Galois simplifié, Math. inform. sci. humaines, 147, 25-46, (1999)
[3] Berry, A.; Bordat, J.-P.; Sigayret, A., Concepts can’t afford to stammer, ()
[4] A. Berry, A. Sigayret, Maintaining class membership information, Workshop on MAnaging of SPEcialization/Generalization HIerarchies (MASPEGHI), Montpellier, France, September 2002, Lecture Notes in Computer Science, Proceedings of the International Conference OOIS’02 (Object-Oriented Information Systems), 2002. · Zbl 1014.68737
[5] A. Berry, A. Sigayret, Representing a concept lattice by a graph, Workshop on Discrete Mathematics and Data Mining, Proceedings of the Second SIAM Conference on Data Mining (SDM’02), Arlington, VA, USA, April 2002, Discrete Appl. Math. 144(1-2) (2004) 27-42, (special issue on Discrete Mathematics and Data Mining).
[6] J.C. Bioch, T. Ibaraki, Version Spaces and Generalized Monotone Boolean Functions, ERIM report (www.erim.eur.nl), ERS-2002-34-LIS (2002).
[7] Birkhoff, G., Lattice theory, (1967), American Mathematical Society Providence, RI · Zbl 0126.03801
[8] Bordat, J.-P., Calcul pratique du treillis de Galois d’une correspondance, Math. inform. sci. humaines, 96, 31-47, (1986) · Zbl 0626.06007
[9] E. Boros, Boolean Functions in: E. Boros, P.L. Hammer (Eds.), Topics in Discrete Mathematics, vol. 10, Elsevier, 1999.
[10] G. Burosch, J. Demetrovics, G.O.H. Katona, The POSet of closures as a model of changing databases, Order, vol. 4, D. Reidel, Dordrecht, 1987, pp. 127-142. · Zbl 0648.06004
[11] Caspard, N.; Monjardet, B., The lattices of closure systems, closure operators and implicational systems on a finite set: a survey, Discrete appl. math., 127, 2, 241-269, (2003) · Zbl 1026.06008
[12] O. Cepek, Structural properties and minimization of Horn Boolean functions, Ph.D. Thesis, RUTCOR, Rutgers University, Piscataway, NJ, USA, 08854, October 1995.
[13] Chen, J.-B.; Lee, S.C., Generation and reorganization of subtype hierarchies, J. object oriented programming, 8, 8, (1996)
[14] C. Delobel, M. Adiba, Bases de données et systèmes relationnels, Dunod, Paris, 1982. · Zbl 0573.68057
[15] Dowling, W.F.; Gallier, J.H., Linear-time algorithms for testing the satisfiability of propositional Horn formulas, J. logic programming, 1, 3, 267-284, (1984) · Zbl 0593.68062
[16] C. Flament, L’analyse booléenne de questionnaires, Mouton, Paris, France, 1976.
[17] B. Ganter, Two basic algorithms in concept analysis, Preprint 831, Technische Hochschule Darmstad, 1984. · Zbl 1274.68484
[18] R. Godin, H. Mili, Building and maintaining analysis-level class hierarchies using Galois lattices, ACM Proceedings OOPSLA’93, Sigplan Notice 28(10) (1993) 394-410 (special issue).
[19] Gouda, K.; Zaki, M.J., Efficiently mining maximal frequent itemsets, ()
[20] Guigues, J.-L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Math. sci. humaines, 95, 5-18, (1986)
[21] Hammer, P.L.; Kogan, A., Horn functions and their DNF’s, Inform. process. lett., 44, 23-29, (1992) · Zbl 0794.68148
[22] Huchard, M.; Dicky, H.; Leblanc, H., Galois lattice as a framework to specify building class hierarchies algorithms, Theoret. inform. appl., 34, 521-548, (2000) · Zbl 0976.06003
[23] Lloyd, J.W., Foundations of logic programming, (1984), Springer Berlin · Zbl 0547.68005
[24] Maier, D., The theory of relational databases, (1983), Computer Science Press MD · Zbl 0519.68082
[25] E. Mephu Nguifo, P. Njiwoua, Using lattice-based framework as a tool for feature extraction, Lecture Notes in Computer Science, Proceedings of the European Conference on Machine Learning (ECML), Chemnitz, Germany, April 1998, Springer, Berlin, vol. 1398, 1998. · Zbl 1088.68731
[26] Minoux, M., LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, Inform. process. lett., 29, 1, 1-12, (1988) · Zbl 0658.68110
[27] Novotný, M., Dependence spaces of information systems, ()
[28] Rose, D.J.; Tarjan, R.E.; Lueker, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[29] E. SanJuan, On Rough Set Analysis applied to Questionnaires, STSM Report, COST Action 15, 1999.
[30] E. SanJuan, Heyting algebra for modeling information retrieval based on thematic clustering, Workshop on Discrete Mathematics and Data Mining, Proceedings of the Second SIAM Conference on Data Mining (SDM’02), Arlington, VA, USA, April 2002.
[31] A. Yahia, L. Lakhal, R. Cicchetti, J.-P. Bordat, iO2, An algorithmic method for building inheritance graphs in object database design, Lecture Notes in Computer Science, Proceedings of the 15th International Conference on Conceptual Modeling (ER’96), Cottbus, Germany, vol. 1157, 1996, pp. 422-437.
[32] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (), 445-470
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.