THE FOUNDATIONS OF TAXONOMIC ENCODING

Taxonomies (partially ordered sets and lattices) are important in many areas of computing science, particularly object-oriented languages, m achine learning, and knowledge representation. Taxonomic encoding stri ves to enhance the efficiency of taxonomic representation and use, whi ch becomes increasingly important as the size of taxonomies grows. In this paper, we describe a formal structure, called a spanning set, in which taxonomic encoding techniques can be characterized. Any taxonomi c encoding scheme implements a mapping from the original ordered set i nto a structure, such as the lattice of bit-vectors or logical terms, in which operations can be performed efficiently. We analyze the funda mental properties any such mapping must satisfy in order to preserve s ubsumption, joins, or meets. Spanning sets are an abstract framework w ithin which we portray and compare existing encoding techniques, and p rovide a context in which new encoding problems can be analyzed, leadi ng to existing, related algorithms or, using other results we develop in this paper, guiding the development of new algorithms. We also expl ore the limits of minimal-sized encodings, proving a lower bound for s imple forms of encoding and showing that, in general, finding minimal- sized encodings is NP-hard. This paper can thus be viewed as both a sy nthesis of current research in taxonomic encoding and a repository of new results and directions for encoding as viewed from the perspective of spanning sets.