**Q:****Do I need to register in order to participate in the competition? Are there any fees?****A:**- No and no.
Participants may optionally register for the competition by sending e-mail to barak+list-abbadingo-request@pearlmutter.net. We will put registered participants on a mailing list for competition-related announcements.

**Q:****How many times should I consult the Oracle?****A:**- Participants should tune their algorithms on their
own time and then submit on the order of one test set labeling per
problem per algorithm. Participants are allowed to rethink their
approach and try again, but they are not allowed to flood our system
with guesses.
To be specific, anyone who deliberately consults the Oracle more than 25 times in one day will be disqualified, as will anyone who mounts any kind of security or denial of services attack against the Abbadingo server.

**Q:**- But what if I have a really really good reason to submit lots and lots of queries to the Oracle, would it be okay then?
**A:***Foolish mortal! Accost not the font of truth with your idle speculations!*The answer would still be no. Nobody is allowed to annoy the Oracle for any reason. The Oracle needs her rest.Figuring out how to generate the best possible hypothesis from the available training data is part of the competition. We provide one useful hint below. You also might want to think about cross-validation.

**Q:****Why doesn't the Oracle provide a score instead of just****PASS**vs**FAIL**?**A:**- That would enable hill climbing on test set performance.

**Q:****How hard are these problems, really?****A:**- That's what we're trying to find out, but they're
supposed to be just beyond the state of the art.
*Short theoretical discussion:*In the worst case, learning DFA's from given data is NP-hard [A-78, PW-93, KV-89]. However, the average case isn't bad [TB-73, L-92, FKRRSS-93]. The problems in this competition are of exactly the same type as described in [L-92], but they are harder than the ones that were successfully solved in that paper because there is less training data. However there is more data than the information theoretic lower bound, so the problems are solvable in principle. Because the amount of training data for these problems lies between current upper and lower sample complexity bounds, the problems are in prime research territory.

**Q:****Do you have any advice?****A:**- A simple way of approaching this competition is to
view it as a pure search problem. The goal of the search is to find
the smallest possible DFA that is consistent with each training set.
The good thing about this approach is that progress can be gauged by
comparing the sizes of the hypothesis DFA's and target DFA's. The
sizes of the targets are listed in the data
sets table. Such a comparison will provide much better feedback
than the competition Oracle.
However, other approaches to the competition are also valid. In fact, participants are not required to produce a DFA at all, only an accurate set of labels for the test set.

**Q:****Is there any publicly available code for doing DFA learning?****A:**- We've made a portable C
implementation of the Trakhtenbrot-Barzdin algorithm [TB-73, L-92] available. It
works great. You should try it on your own DFA learning tasks. Note,
though, that the competition has been specifically designed so that
the twelve non-practice problems are too hard for this program.
There is also a R

^{4}RS Scheme implementation of the Trakhtenbrot-Barzdin algorithm available. This Scheme code has not been optimized, and is orders of magnitude slower than the C version. For expository purposes only.In order to avoid biasing participants we are not publishing our own library of routines for DFA manipulation, minimization, etc. However if you have any source code, useful calculations, or anything else you'd like to share with other participants, we will gladly make them available in the collection of generously donated materials.

You might also want to search the self-proclaimed Homepage for the International Grammatical Inference Community.

**Q:****What happened to the linear ranking of the problems?****A:**- We replaced that system (as of Mar 18) because it didn't provide an incentive for progress in both of the directions that we care about, namely towards larger target concepts and towards sparser training data. Given that we set up the problems on a 2-dimensional grid, we needed an incentive system that respects that grid.

**Q:****Where are the solutions and target DFA's being stored?****A:**- Not on any computer anywhere. The Abbadingo
Oracle recognizes solutions using cryptographic checksums that are
exceedingly difficult to invert and have the nice property of throwing
away lots of information. The official training set files are the
*only files anywhere online*that contain enough information to construct winning solutions for this competition.

**Q:****Does Abbadingo have a PGP public key?****A:**- You may use Barak Pearlmutter's PGP public key, available on the public PGP keyserver network.

**Q:****Would it be possible to use SSL to access the Oracle?****A:**- Yes. You can access the entire Abbadingo site via SSL, including the Oracle.

**Q:****What's to prevent you from doing something fishy with the target DFA's?****A:**- At the end of the competition we will release two
tar files which together contain all of the target DFA's. The first
will cover problems D, R, S, and T, and has MD5 checksum
`5de2a2c015145a82a99d8886d447f74e`. The second covers the remaining problems, A, B, C, 1, 2, 3, 4, 5, 6, 7, 8, and 9, and has MD5 checksum`4846e75421f9af78998b5faf229c72d6`.

**Q:****How were the strings in the training and testing sets generated? Were they drawn from the same distribution?****A:**- The training and testing sets were drawn without replacement from a uniform distribution over the set of all strings not longer than 5 plus the target DFA depth [L-92, section 2.1].

**Q:****How can I be sure the sparser training sets fully constrain the target DFA?****A:**- How can you be sure that, when it next rains, by
coincidence the right half of one square of the sidewalk in front of
your house won't stay dry while the other half gets wet? You can't be
sure. All you can do is calculate the odds.
It is a straightforward exercise to find a closed form expression that approximates the distribution of the number of nodes/links not terminated at/traversed by the training set as a function of the training set size.

It may be that some of the sparser training sets do not fully constrain the solution. Even if they don't, it might be that the error rate induced by missing information would be below the 1% tolerance.

Doing the best you can with limited data is part of the competition.

**Q:****You say ``The secret target concepts were drawn from a uniform distribution over DFA's.'' How?****A:**- The distribution over possible target DFA's was
defined by the following algorithm. To generate a random DFA with
roughly
*N*states start with a digraph containing 5/4*N*nodes and no edges. From each node add two outgoing edges, with the destination nodes chosen randomly from a uniform distribution over the 5/4*N*nodes. Pick a random node and call it the start state. Discard all nodes that aren't reachable from the start state. For each state flip a fair coin to choose between the labels*accept*and*reject*. Run the Moore minimization algorithm on the DFA. Finally, start over if the DFA's depth isn't exactly (2 log_{2}*N*)-2 rounded to the nearest integer. **Q:****So the numbers in the problem parameters table were calculated after Moore minimization?****A:**- Yes.

**Q:****What does the ``target DFA depth'' listed in the problem parameters table mean?****A:**- The depth of a DFA is the maximum over all states
of the length of the shortest string which leads to that state:
depth = max

This terminology extends the notion of the depth of a tree in the natural way, and was used by Trakhtenbrot and Barzdin' [TB-73]._{{s|states}}min_{{x|strings leading to s}}length(x)

**Q:****Is it ethical to use the given DFA depths and node counts?****A:**- There is no rule against their use. We don't think they'd be much help, but would be interested to find otherwise. You certainly wouldn't win any special mention for elegance!

**Q:****Is it ethical to use lots of computer time?****A:**- Yes.

**Q:****What does Abbadingo mean?****A:**- [S-61]

- [A-78]
- Dana Angluin. On the complexity
of minimum inference of regular sets. Information and Control,
**39***(3)*pages 337-350, 1978. - [FKRRSS-93]
- Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert Schapire, and Linda Sellie. Efficient learning of typical finite automata from random walks. In Proceedings of the Twenty Fifth Annual Symposium on Theory of Computing, pages 315-324, May 1993.
- [KV-89]
- Michael Kearns and Leslie
G. Valiant. Cryptographic
limitations on learning Boolean formulae and finite
automata. In Proceedings of the Twenty First Annual
Symposium on Theory of Computing, pages 433-444, May 1989. See
also Journal of the ACM,
**41***(1)*pages 67-95, 1994. [jacm archive] - [L-92]
- Kevin J. Lang. Random DFA's can be approximately learned from sparse uniform examples. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, pages 45-52, July 1992.
- [PW-93]
- Leonard Pitt and Manfred K.
Warmuth. The minimum consistent DFA problem cannot be
approximated within any polynomial. Journal of the ACM,
**40***(1)*pages 95-142, January 1993. [jacm archive] - [S-61]
- Cordwainer Smith. Alpha Ralpha Boulevard. Fantasy and Science Fiction, June 1961.
- [TB-73]
- Boris Avraamovich Trakhtenbrot and Ya Martynovich Barzdin'. Finite Automata: Behavior and Synthesis, Amsterdam: North-Holland, 1973.

Abbadingo home

The Abbadingo Webmaster welcomes your comments and complaints.