The Abbadingo One competition is over.Plans are being made for Abbadingo 2, with new sorts of problems.A test version of a follow-on to Abbadingo One (but

notAbbadingo Two, which will be different) called Gowachin, is now available for your grammar learning pleasure.Meanwhile, here is a forthcoming paper describing the outcome of the first competition, which will appear in the volume of Springer-Verlag's Lecture Notes in Computer Science containing the proceedings of ICGI-98. And here is an expanded version of the ICGI-98 paper, currently in review by a journal. And here is code for 4 DFA learning algorithms, including 3 versions of Rodney Price's EDSM idea. These 3 programs can solve Abbadingo problems 1, 2, 3, R, 4, 6, and S.

This research competition is based on grammar induction, a difficult problem in machine learning. The winners will receive scientific admiration, one thousand twenty four dollars, guest of honor status at a formal award ceremony, and more.

Read the description, | Mid-Level Executive Summary |

read the details and clarifications, | |

learn from the data sets, | Announcement for Technical Forums |

satisfy the Abbadingo Oracle, | |

then email the administrators! | Press Release for General Distribution |

Nov 15- The competition is over. Congratulations to the winners Rod Price and Hugues Juille!
Jul 14- Hugues Juille solves problem 7, thereby proving that the rightmost column is
notimpossible!Jun 8- Problem 6 has fallen.
May 16- Rod Price nails problem S!
May 15- Problem R has fallen.
May 6- Problem 3 has fallen.
Mar 31- Problem 5 has fallen.
Mar 19- Problem 2 has fallen.
Mar 18- We have adopted a 2-dimensional partial ordering for the benchmark problems that makes more sense given that the problems are layed out on a 2-dimensional grid. We can now not only measure, but also reward progress in both of the two directions that we care about, namely towards larger target concepts and towards sparser training data. This change has the side effect of allowing multiple winners if people produce algorithms that excel in different ways.
Mar 14- Problem 4 has fallen.
Mar 10- Problem 1 has fallen.
Mar 7- Abbadingo One competition begins.

- There are 16 benchmark problems. Each problem consists of a secret
randomly generated DFA which serves as a target concept, a set of
training strings which have been labeled by that target concept,
and a set of unlabeled testing strings.
- The task is to predict the labels that the target concept would
assign to the testing strings.
Each problem will be considered solved by the first person to
demonstrate to us a test set error rate of 1% or less.
- The problems are ranked according to two factors that affect
their difficulty: the size of the target concept and the sparsity of the
training data.
The winners of the competition will the first participants to solve
problems that aren't easier than problems solved by other
participants before the end of the competition, where ``easier''
is measured on a two-dimensional
dominance lattice.
Because some pairs of problems are of incomparable difficulty, the
competition might end up with multiple winners. We will be happy
to reward multiple algorithms that excel in different ways.
- We will not disclose any test set answers during the competition.
Instead we provide the Abbadingo
Oracle which can recognize sufficiently accurate submissions.
- The output of the oracle is either
**PASS**or**FAIL**. - When the Oracle declares a test set labeling to be a valid
solution, the competitor must contact the Abbadingo
administrators in order to receive official credit. Before
awarding official credit the administrators will manually verify the
correctness and priority of the labeling.
Even though the automatic Oracle is not empowered to give official
credit, participants are required to obtain its permission before
submitting proposed solutions to the competition administrators.
- The competition ends on (7:00 pm GMT, Nov. 15, 1997)
- The 16 benchmark problems include 4 problems that we already know how to solve, and hence are for practice purposes only, and 12 official challenge problems.

So far nine of the twelve challenge problems have been solved. Solved problems are noted in the data sets page, which has pointers to the data sets along with a table of the problems, their current status, and some numbers relating to their difficulty.

This competition was inspired by a call for good benchmark tasks during the AAAI-96 Fall Symposium on Learning Complex Behaviors in Adaptive Intelligent Systems. It is being organized and administered by Kevin J. Lang and Barak A. Pearlmutter.

- The Computer Science
Department at the University of
New Mexico, which provided the Abbadingo server.
- The prestigious Kluwer Academic journal Machine Learning,
which promised to give priority treatment to a paper describing the
award winning algorithm.
- The Santa Fe Institute.
- The Journal of
Artificial Intelligence Research.
- Private individuals who have contributed to the award fund. Some of them may be listed here in the future.

Intellectual Property:We make no claims on the intellectual property of competition participants.

Money:All donated funds will be used solely for awards and reimbursing the award ceremony travel expenses of award winners. If there is any prize money left over after the competition it will be returned to the sponsors, unless they'd prefer that it be rolled over into Abbadingo Two.

Void Where Prohibited:Participants must obey all laws and regulations that apply to them. If anyone's government or employer prohibits them from participating in this competition or from claiming an award, then they must not do so. Similarly, winners are responsible for paying any taxes that might be required.

General Disclaimer:The organizers and administrators of the Abbadingo competition (Kevin J. Lang and Barak A. Pearlmutter) reserve the right to change the competition in any way at any time at their sole discretion, without notice, including the right to change the rules, problems, and awards, and the right to terminate the competition. The Abbadingo administrators are the sole arbiters for this competition, and their judgment is final in all matters.

Eligibility:The administrators and their immediate relatives and immediate co-workers are not eligible for any award.

The Abbadingo Webmaster welcomes your comments and complaints.