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 F-34392 MONTPELLIER 5 FRANCE UNIV MONTPELLIER 2 F-34392 MONTPELLIER 5 FRANCE
Titolo Testata:
Theoretical computer science
fascicolo: 2, volume: 165, anno: 1996,
pagine: 391 - 405
SICI:
0304-3975(1996)165:2<391:TSFDLA>2.0.ZU;2-L
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. 391-405

Abstract

From a well-known 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 bit-vector encoding for distributive lattices can beeasily derived from this data structure. Relationships with encoding proposed by Ait-Kaci 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