  Conditional preference statements have been used to compactly represent
preferences over combinatorial domains. They are at the core of CP-nets and
their generalizations, and lexicographic preference trees. Several works have
addressed the complexity of some queries (optimization, dominance in
particular). We extend in this paper some of these results, and study other
queries which have not been addressed so far, like equivalence, thereby
contributing to a knowledge compilation map for languages based on conditional
preference statements. We also introduce a new parameterised family of
languages, which enables to balance expressiveness against the complexity of
some queries.
