Construction of minimal, deterministic, acyclic finite-state automata from sets of strings

Algorithms implemented and compared

Results and recommendations for building minimal automata

Pseudo-minimal Automata

This version of adfa also construct pseudo-minimal automata. For each word in the language of the automaton, there is a transition (called proper transition that is not shared with any other word. That proper transition can be used carry word-specific information. The words on input must end with a special end-of-word marker that is not part of the alphabet of words (e.g. #). Otherwise apart from proper transitions, we would have proper states as well.

Software

The software used in the experiments is available in source form free of charge for non-commercial purposes. I want to put it under GNU Public Licence once I read it and understand it in full. adfa builds automata, and displays some statistics, but the automata are not saved. This was simply not needed for the experiments. I'm sorry if you are disappointed.

Further information

The experiments were conducted for the paper I sumbitted to the Conference on Implementation of Automata and Applications. Proceedings of that series of Conferences are printed by Springer, and the publisher asks the authors not to put their papers on their websites for one year after publication. So here is a draft.

You can find more information about finite-state automata, minimization, etc. on a page about FSA related algorithms. You can look at my two fully functional software packages implementing two of the above algorithms. The automata I use there are a bit different - they have final transitions instead of final states. This makes them a bit smaller than traditional automata. The packages are for use in the natural language processing domain. You may also want to look at my publications.

The algorithms in the adfa package operate on acyclic automata, i.e. automata without cycles. Some people find this page while looking for general minimization algorithms. They should rather look at http://www.eti.pg.gda.pl/~jandac/minim.html, a page dedicated to minimization of automata with cycles.
Jan Daciuk