Incremental Minimalization of Deterministic

Acyclic Finite State Automata

This is a topic i've been digging up in the web while researching for an efficient way to implement the tab-completion in CDG. Its mainly about saving huge Lists of Strings in the most memory-saving way possible. Constructing a DFA whose accepted Language is exactly that finite Set of Strings seamed a reasonable approach and led to the conclusion, that DFAs accepting finite Languages are always acyclic.

Traditional minimalization Algorithms for DFAs are always taking an DFA as input and returning a minimalized one. This approach is not usafull in this case, because constructing the complete DFA before minimalization would cost as much memory as we wanted to save.

These are some papers I found around the web on exactly that topic:

free:

• Incremental Construction of Minimal Acyclic Finite State Automata
• Contructing minimal acyclic deterministic Finite State Automata

must be paid for:

• Bruce W. Watson: A new algorithm for the construction of minimal acyclic DFAs

Acyclic FSA can also be used as a perfect hashing Function. An Implementation would be to store in each state a number representing the number of reachable end-nodes starting from this node. When traversing the tree in order to look up a word one can sum up all numbers of previous nodes to get an unique tree path address.

Further Information can be found at: * Finite State Automata & Directed Acyclic Graphs

-- BjoernEngelmann -- 01 Apr 2005