Premium
An Algorithm for Minimal Insertion in a Type Lattice
Author(s) -
Valtchev Petko
Publication year - 1999
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00082
Subject(s) - lattice (music) , partially ordered set , algorithm , mathematics , computation , combinatorics , maximal element , dedekind cut , complete lattice , discrete mathematics , computer science , set (abstract data type) , physics , condensed matter physics , universality (dynamical systems) , acoustics , programming language
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.