Learning lexicographic orders

The purpose of this paper is to learn the order of criteria of lexicographic decision under various reasonable assumptions. We give a sample evaluation and an oracle based algorithm. In the worst case analysis we are dealing with the adversarial models. We show that if the distances of the samples are less than 4, then it is not learnable, but 4-distance samples are polynomial learnable.