La dimension comme paramètre du codage des ordres

Un ensemble d'éléments muni d'une relation d'ordre est appelé un ordre partiel. Pour un ordre (P,<), savoir si deux éléments x et y sont comparables est une question majeure. Dans l'objectif de répondre efficacement à cette question, des codages particuliers (structures de données et algorithmes) ont été introduits. Ces codages sont appelés codages hiérarchiques. Les deux principaux critères à respecter lors de la conception de tels codages sont l'efficacité du calcul à l'exécution (les tests de subsumption doivent être très rapides), et la minimisation de l'espace de stockage du code affecté à chaque élément de l'ordre. Dans notre exposé nous montrerons comment le codage d'un ordre se ramène à un problème de plongement dans une structure plus simple disposant de propriétés intéressantes. Nous parlerons en particulier des plongements dans des produits de chaînes.