Abbadingo One: DFA Learning Competition

The Abbadingo One competition is over. Plans are being made for Abbadingo 2, with new sorts of problems.

Precolumbian Gowachin Fetsh A test version of a follow-on to Abbadingo One (but not Abbadingo 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.

High-Level Executive Summary

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

Recent News

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 not impossible!
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.


This competition's topic is average case learnability of deterministic finite automata from given training data. The basic setup is:

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.

Details and Clarifications

For more details see the Page of Technical Details and Miscellaneous Clarifications in Q&A Form. Please read that document before using the Oracle! Requests for clarifications are welcome. We will post the responses to the above page, so that everyone can see them.


Abbadingo One is sponsored by: If you'd like to help raise the stakes, or if your institution would like to become a sponsor, please contact the organizers.

The Fine Print

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.