Soft constraints for lexicographic orders

While classical Constraint Satisfaction Problems (shortly, CSPs) concern the search for the boolean assignment of a set of variables that has to satisfy some given requirements, its soft variant considers more general, possibly ordered domains for assignments, thus modelling preferences: the aim is to provide an environment where suitable algorithm and properties (e.g. on constraint propagation) can be stated and proved, and thus inherited by all the instances. Besides their flexibility, these formalisms have been advocated for their modularity: suitable operators can be dened, in order to manipulate such structures and build new ones. However, some intuitive constructions were given less attention, such as lexicographic orders. Given two partially ordered domains, our work shows under which conditions a new one can be built that corresponds to the lexicographic order of those two. The result allows for a wider application of the soft formalism, and it is going to be pivotal for the use of soft constraints in modelling scenarios where more than one feature has to be satised, yet the features themselves are equipped with a fixed order of importance.