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.

- Determinization
- Determinization of Transducers
- Minimization
- Practical Experience
- Availability
- Acknowledgements

1998-09-28