Description of the 2-dimensional partial ordering on benchmark problems

The goal of the Abbadingo competition is to encourage the development of new DFA induction algorithms that can deal with than ever before. We want to encourage progress in either of these directions. Therefore, the Abbadingo challenge problems are ranked according to the 2-dimensional partial ordering defined by the following matrix, in which larger targets are found by moving down, while sparser training data is found by moving right.

training set coverage
dense sparse
target
DFA
size		 small A 1 4 7
B 2 5 8
large C 3 6 9
D R S T

The rule is that a problem x dominates a problem y if they are in the same column and x is below y, or if they are in the same row and x is to the right of y, or if x is below and to the right of y. For example, 5 dominates 1, 4, and 2; S dominates 1, 2, 3, R, 4, 5, and 6.

This is a partial ordering because some pairs of problems are incomparable, for instance 8 and S. If we end up with different participants maxed out on incomparable problems, we will declare multiple winners. The exact rule is this: the first person to solve a problem owns it. At the end of the competition, winners will be people who own problems that aren't dominated by problems owned by someone else.

Additional notes

In the above table, problems dominated by a problem already owned are colored gray. Problems already owned but not dominated are colored pink.

Problems A, B, C, and D are for practice only because they are easily solvable by the Trakhtenbrot-Barzdin program that we have made available. Problems D, R, S, and T were added on Mar 18 in response to requests for larger problems. Their target DFA's contain around 512 states. For further information on problem parameters, or to download, see the data sets page.

Competition status

The front-runners are Rod Price, who owns problem S, and Hugues Juille, who owns problem 7. You can beat them both by solving problem T, or beat Hugues Juille and join Rod Price by solving problem 8.

Abbadingo home
The Abbadingo Webmaster welcomes your comments and complaints.