Generalizations of Semiorders: A Review Note
Semiorders may form the simplest class of partially ordered sets that accommodate thresholds of discriminability in binary comparisons. Many other classes of ordered sets that generalize the uniform-threshold feature of semiorders have been studied in recent years. This note describes a variety of generalizations and their interrelationships, including equivalences and proper inclusions between classes. Nine nonequivalent classes are designated as interval orders, bisemiorders, split semiorders, unit tolerance orders, unit bitolerance orders, tolerance orders, bitolerance orders, semitransitive orders, and subsemiorders. Each is defined by an interval representation or by a few minimal forbidden configurations. All proper inclusions between classes are identified along with equivalences to other classes. Copyright 1997 Academic Press. Copyright 1997 Academic Press
Fishburn
PC
AT & T Labs-Research, Florham Park, New Jersey, 07932