Valtchev, Petko
(1999).
« An Algorithm for Minimal Insertion in a Type Lattice ».
Computational Intelligence, 15(1), pp. 63-78.
Fichier(s) associé(s) à ce document :
Résumé
The problem of inserting a new element x into a lattice of types L is addressed in the paper. As the poset L+x obtained by the direct insertion of x in L is not necessarily a lattice, some set of auxiliary elements should be added to restore the lattice properties. An approach toward the lattice insertion is presented which allows the set of auxiliary elements to be kept minimal. The key idea is to build the final lattice L+ as isomorphic to the Dedekind–McNeille completion of the order L+x. Our strategy is based on a global definition of the set of auxiliary elements and their locations in L+. Each auxiliary is related to a specific element of L, an odd, which represents GLB (LUB) of some elements in L superior (inferior) to x. An appropriate computation scheme for the auxiliary types is given preserving the subtyping in the lattice L+. The insertion strategy presented is more general than the existing ones, since it deals with general kinds of lattices and makes no hypothesis on the location of x in L. An algorithm computing L+ from L and x of time complexity O(|L||J(L)|ω^3(L)) is provided.
Altmetric
Altmetric
RECHERCHER
PARCOURIR
LIBRE ACCÈS
