An on-line learning algorithm for pruning state space search
is described in this paper. The algorithm is based on a finite state machine
which is both created and used in the search. The pruning technique
is necessary when memory resources in searching huge problem spaces
are restricted. A duplicate sequence is a generating path in the search
tree that has a counterpart with smaller weight. The automaton provides
the dictionary operations Insert and Delete for the duplicate sequences
found in the search, and Search for pruning the search tree.
The underlying data structure is a multi suffix tree. Given that the alphabet
of state transitions is bounded by a constant an optimal worst-case
bound of O(|m|) for both insertion and deletion of a duplicate sequence m
is achieved. Using the structure as a finite state machine
we can incrementally accept a given sequence x in time O(|x|).