Automata Library for Haskell

What is it?

This library implements deterministic and non-deterministic finite automata in the programming language Haskell. Numerous standard and esoteric automata constructions are implemented, from minimization and intersection, to quotients and strongly-connected components.

This library is unique because it implements the formal textbook definition of automata directly. This novel representation offers potentially exponential memory savings over the nearly universal representation of automata as arrays of states or lookup tables. It also offers some interesting time tradeoffs. As the traditional representation is subsumed by the new representation, the new representation can always be used in a way that mimics the time complexity of the old.

Direct implementation is possible because Haskell offers higher-order functions, which result when nested function declarations and first-class functions are combined in a meaningful way. (i.e. the lambda calculus) This approach simply is not practical in languages such as C++ and Pascal. This technique is safe because Haskell is purely functional; no function can produce a side-effect. With side-effects this approach requires more discipline but is still applicable.

All this and more is described in the paper A Collection of Functional Libraries for Theory of Computation presented at the 39th ACM Southeast Conference.

License:

Downloads:

• Automata.hs, the library itself
• tests.hs, some tests and examples for the library.
• Tree234.hs, Top-down 2-3-4 balanced trees.
• Tree234Map.hs, Associative collections for Edison based on Tree234.hs.

Notes:

You will need a copy of GHC 5, preferably with GHCi, to use this software. I know this software works with GHC 5.04.3, 5.02.x may work as well. To run the software, put the files in the same directory and use the command line

ghci -fglasgow-exts -package data tests.hs

This library uses Edison's interfaces to sets and finite maps. Edison is a rather nice library of data structures by Chris Okasaki. It provides interfaces to sequences, sets, and finite maps, and implements a variety of efficient data structures for each. However, it has been left in a somewhat incomplete state. In particular, it does not provide maps on ordered keys, which our library needs. Tree234Map fixes this. In my opinion, Edison is significantly better than C++'s Standard Template Library (STL), and the Haskell community would benefit greatly from people using and contributing to it more.

To Do:

• Export the type constructors DFA and NFA abstractly to enable future performance hacking
• Write documentation
• Create more tests
• Come up with a better name

Planned Future Work:

• Implement an (n * log n) minimization algorithm.
• Implement Mealy Machines.
• Performance tuning
• Add tools for the (semi-)automatic visualization of automata.

Possible Future Work:

• Investigate different ways of labeling edges and states of NFA and DFA with properties. (i.e. Kripke structures).
• Implement a model-checking algorithm for some suitable temporal logic, such as CTL or CTL*.
• Add more variations on automata. (Alternating automata?)
• Anything useful users want.
• Donate the library to hslibs.

Last modified: Tue Apr 30 22:11:41 EDT 2002