×

Galois lattice as a framework to specify building class hierarchies algorithms. (English) Zbl 0976.06003

Summary: In the context of object-oriented systems, algorithms for building class hierarchies are currently receiving much attention. We present here a characterization of several global algorithms. A global algorithm is one which starts with only the set of classes (provided with all their properties) and directly builds the hierarchy. The algorithms scrutinized were developed each in a different framework. In this survey, they are explained in a single framework, which takes advantage of a substructure of the Galois lattice associated with the binary relation mapping the classes to their properties. Their characterization allows to figure the results of the algorithms without running them in simple cases. This study once again highlights the Galois lattice as a main and intuitive model for class hierarchies.

MSC:

06A15 Galois correspondences, closure operators (in relation to ordered sets)
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] M. Barbut and B. Monjardet, Ordre et classification : Algèbre et combinatoire. Hachette (1970). Zbl0267.06001 · Zbl 0267.06001
[2] J.-B. Chen and S.C. Lee, Generation and reorganization of subtype hierarchies. J. Object Oriented Programming 8 (1996).
[3] N. Chevalier, M. Dao, C. Dony, M. Huchard, H. Leblanc and T. Libourel, An environment for building and maintaining class hierarchies, in ECOOP 99 Workshop - Object-Oriented Architectural Evolution (1999).
[4] W.R. Cook, Interfaces and Specifications for the Smalltalk-80 Collection Classes, in Special issue of Sigplan Notice - Proceedings of ACM OOPSLA’92 (1992) 1-15.
[5] B.A. Davey and H.A. Priestley, Introduction to Lattices and Orders. Cambridge University Press (1990). · Zbl 0701.06001
[6] H. Dicky, C. Dony, M. Huchard and T. Libourel, On automatic class insertion with overloading, Special issue of Sigplan Notice - Proceedings of ACM OOPSLA’96, Vol. 31 (1996) 251-267.
[7] R. Godin and H. Mili, Building and Maintaining Analysis-Level Class Hierarchies Using Galois Lattices, in Special issue of Sigplan Notice - Proceedings of ACM OOPSLA’93, Vol. 28 (1993) 394-410.
[8] R. Godin, H. Mili, G. Mineau and R. Missaoui, Conceptual Clustering methods based on Galois lattices and applications. Revue d’intelligence artificielle 9 (1995).
[9] R. Godin, G. Mineau and R. Missaoui, Incremental structuring of knowledge bases, in Proc. of International KRUSE symposium: Knowledge Retrieval, Use, and Storage for Efficiency. Springer-Verlag, Lecture Notes in Artificial Intelligence 9 (1995) 179-198.
[10] R. Godin, H. Mili, G. Mineau, R. Missaoui, A. Arfi and T.T. Chau, Design of Class Hierarchies Based on Concept (Galois) Lattices. Theory And Practice of Object Systems 4 (1998).
[11] M. Huchard and H. Leblanc, Computing Interfaces in Java, in Proc. of IEE International conference on Automated Software Engineering (ASE’2000). Grenoble, France (2000) 317-320.
[12] K.J. Lieberherr, P. Bergstein and I. Silva-Lepe, From objects to classes: Algorithms for optimal object-oriented design. J. Software Engrg. (1991) 205-228.
[13] G. Mineau, J. Gecsei and R. Godin, Structuring Knowledge Bases Using Automatic Learning, in Proc. of the sixth International Conference on Data Engineering (1990) 274-280.
[14] I. Moore and T. Clement, A Simple and Efficient Algorithm for Inferring Inheritance Hierarchies, in TOOLS Europe 1996 Proceedings. Prentice-Hall (1996).
[15] B. Stroustrup, The C++ programming language, third edition. Addison-Wesley (1998). · Zbl 0825.68056
[16] R. Wille, Restructuring lattice theory: An approach based on hierarchies of concepts, Ordered Sets, edited by I. Rivals (1982) 23. · Zbl 0491.06008
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.