Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Encoding of multiple inheritance hierarchies and partial orders
Autore:
Caseau, Y; Habib, M; Nourine, L; Raynaud, O;
Indirizzi:
Bouygues, F-78061 St Quentin En Yvelines, France Bouygues St Quentin En Yvelines France F-78061 entin En Yvelines, France CNRS, LIRMM, F-75700 Paris, France CNRS Paris France F-75700CNRS, LIRMM, F-75700 Paris, France Univ Montpellier, F-34059 Montpellier, France Univ Montpellier Montpellier France F-34059 F-34059 Montpellier, France
Titolo Testata:
COMPUTATIONAL INTELLIGENCE
fascicolo: 1, volume: 15, anno: 1999,
pagine: 50 - 62
SICI:
0824-7935(199902)15:1<50:EOMIHA>2.0.ZU;2-X
Fonte:
ISI
Lingua:
ENG
Keywords:
type inclusion; bit vector; subsumption; taxonomy encoding; partial order; lattice;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
22
Recensione:
Indirizzi per estratti:
Indirizzo: Caseau, Y Bouygues,nceallenger 1,Av E Freyssinet, F-78061 St Quentin En Yvelines, Fra Bouygues Challenger 1,Av E Freyssinet St Quentin En Yvelines France F-78061
Citazione:
Y. Caseau et al., "Encoding of multiple inheritance hierarchies and partial orders", COMPUT INTE, 15(1), 1999, pp. 50-62

Abstract

Efficient implementation of type inclusion is an important feature of object oriented programming languages with multiple inheritance. The idea is toassociate to each type a subset of a set S = {1,..., k} such that type inclusion coincides with subset inclusion. Such an embedding of types into 2(S) (the lattice of all subsets of S) is called a bit-vector encoding of the type hierarchy. In this paper, we show that most known bit-vector encoding methods can be inserted on a general theoretical framework using graph coloration, namely the notion of a simple encoding. We use the word simple because all these methods are heuristics for the general bit-vector encoding problem, known as the 2-dimension problem. First we provide a correct algorithm for partial orders based on simple encoding, improving the algorithm of Krall, Vitek, and Horspool (1997). Second we show that finding an optimal simple encoding is an NP-hard problem. We end with a discussion on some practical issues.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 02/04/20 alle ore 02:20:03