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.
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.