Catalogo Articoli (Spogli Riviste)
OPAC HELP
Titolo: TREE STRUCTURE FOR DISTRIBUTIVE LATTICES AND ITS APPLICATIONS
Autore: HABIB M; NOURINE L;
 Indirizzi:
 LIRMM,CNRS UMR C09928,161 RUE ADA F34392 MONTPELLIER 5 FRANCE UNIV MONTPELLIER 2 F34392 MONTPELLIER 5 FRANCE
 Titolo Testata:
 Theoretical computer science
fascicolo: 2,
volume: 165,
anno: 1996,
pagine: 391  405
 SICI:
 03043975(1996)165:2<391:TSFDLA>2.0.ZU;2L
 Fonte:
 ISI
 Lingua:
 ENG
 Tipo documento:
 Article
 Natura:
 Periodico
 Settore Disciplinare:
 CompuMath Citation Index
 Science Citation Index Expanded
 Citazioni:
 25
 Recensione:
 Indirizzi per estratti:



 Citazione:
 M. Habib e L. Nourine, "TREE STRUCTURE FOR DISTRIBUTIVE LATTICES AND ITS APPLICATIONS", Theoretical computer science, 165(2), 1996, pp. 391405
Abstract
From a wellknown decomposition theorem, we propose a tree representation for distributive and simplicial lattices. We show how this representation (called ideal tree) can be efficiently computed (linear time in the size of the lattice given by any graph whose transitive closureis the lattice) and compared with respect to time and space complexity. As far as time complexity is concerned, we simply consider the timeneeded for computations of basic lattice operations such as meet or join and reachability (x less than or equal to y). Therefore an ideal tree can be considered as a good data structure for a distributive lattice, since for a lattice L = (X,E) it uses O(\X\) space and allows computations of reachability, meet and join operations in O(\M(L)\), where M(L) denotes the suborder of the meet irreducible elements in L. Furthermore, optimal bitvector encoding for distributive lattices can beeasily derived from this data structure. Relationships with encoding proposed by AitKaci et al. [3], Caseau [5] are also discussed. Intensive use of this ideal tree allow us to achieve best running time algorithms for most of the applications in which distributive lattices are involved; as for example, constructing the lattice of ideals or generating ideals for a given partial order. Therefore this data structure can be used in many areas such as scheduling theory, in which several algorithms are based on a dynamic programming approach of the lattice of ideals of the precedence ordering; or distributed programming, in which some of the debugging tools rely on the calculation of the latticeof ideals of the causality ordering of the events.
ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 29/03/20 alle ore 15:19:41