Book chapter
Open access

Near Optimal Hierarchical Encoding of Types

Published inObjects at large = Objets en liberté, Editors Tsichritzis, Dionysios, p. 101-113
PublisherGenève : Centre universitaire d'informatique
Publication date1997-07

A type inclusion test is a procedure to decide whether two types are related by a given subtyping relationship. An efficient implementation of the type inclusion test plays an important role in the performance of object oriented programming languages with multiple subtyping like C++, Eiffel or Java. There are well-known methods for performing fast constant time type inclusion tests that use a hierarchical bit vector encoding of the partial ordered set representing the type hierarchy. The number of instructions required by the type inclusion test is proportional to the length of those bit vectors. We present a new algonthm based on graph coloring which computes a near optimal hierarchical encoding of type hierarchies. The new algorithm improves significantly on previous results - it is faster, simpler and generates smaller bit vectors.

Citation (ISO format)
KRALL, Andréas, VITEK, Jan, HORSPOOL, R. Nigel. Near Optimal Hierarchical Encoding of Types. In: Objects at large = Objets en liberté. Genève : Centre universitaire d’informatique, 1997. p. 101–113.
Main files (1)
Book chapter (Published version)
  • PID : unige:155394

Technical informations

Creation10/13/2021 10:34:00 AM
First validation10/13/2021 10:34:00 AM
Update time03/16/2023 1:30:22 AM
Status update03/16/2023 1:30:21 AM
Last indexation08/31/2023 1:59:14 AM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack