next up previous
Next: Determinization Up: FSA Utilities: A Toolbox Previous: The Tk Widget

A note on Implementation

Prolog is a high-level language in which operations on finite-state automata can be implemented rather straightforwardly.

However, Prolog lacks the appropriate data-structures to implement e.g. the subset-construction algorithm as efficiently as possible. For this reason I have developed a library which implements a data-structure which approximates a hash-table: this data-structure provides log time access rather than constant time access.

Furthermore, note that Prolog's built-in search method (backtracking) is not used in the implementation of the determinization and minimization operations. These operations are implemented by deterministic algorithms. If we are careful in designing the Prolog code for these algorithms, then the resulting Prolog code can be run efficiently, because modern Prolog compilers are capable of recognising determinism.

Noord G.J.M. van