First EAI International Conference on Computer Science and Engineering

Research Article

Encoding Partial Orders Through Modular Decomposition

Download1042 downloads
  • @INPROCEEDINGS{10.4108/eai.27-2-2017.152339,
        author={Laurent Beaudou and Kaoutar Ghazi and Giacomo Kahn and Olivier Raynaud and Eric Thierry},
        title={Encoding Partial Orders  Through Modular Decomposition},
        proceedings={First EAI International Conference on Computer Science and Engineering},
        publisher={EAI},
        proceedings_a={COMPSE},
        year={2017},
        month={3},
        keywords={Bit-vector encodings; 2-dimension; Modular decomposition Series-parallel partial orders; Embeddings; Heuristics},
        doi={10.4108/eai.27-2-2017.152339}
    }
    
  • Laurent Beaudou
    Kaoutar Ghazi
    Giacomo Kahn
    Olivier Raynaud
    Eric Thierry
    Year: 2017
    Encoding Partial Orders Through Modular Decomposition
    COMPSE
    EAI
    DOI: 10.4108/eai.27-2-2017.152339
Laurent Beaudou1,*, Kaoutar Ghazi, Giacomo Kahn, Olivier Raynaud, Eric Thierry
  • 1: Limos laboratory, Blaise Pascal University, 63000 Clermont-Ferrand, France
*Contact email: laurent.beaudou@univ-bpclermont.fr

Abstract

A well-known method to represent a partially ordered set P consists in associating to each element of P a subset of a fixed set S ={1,...,k} such that the order relation coincides with subset inclusion. Such an embedding is called a bit-vector encoding of P and is economical with space. As a consequence, they have found applications in knowledge representation, distributed computing or object-oriented programming. The smallest size of such an encoding is called the 2-dimension of P and its computation is known to be NP-hard in the general case [12]. Finding heuristics which provide compact encodings is challenging and it has yielded many works. Our paper presents a new heuristic through modular decomposition. This unified process is a 4-approximation for rooted trees 2-dimension and provides reduced encoding by 40% for series-parallel posets. It reaches or improves the best results for general posets.