An Algorithm for Minimal Insertion in a Type Lattice

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 :
Télécharger (277kB)


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.

Type: Article de revue scientifique
Mots-clés ou Sujets: type lattices;lattice insertion;Dedekind-McNeille completion
Unité d'appartenance: Faculté des sciences > Département d'informatique
Déposé par: Petko Valtchev
Date de dépôt: 27 avr. 2016 13:38
Dernière modification: 19 mai 2016 18:11
Adresse URL :


Voir les statistiques sur cinq ans...