Improving RPNI Algorithm using Minimal Message Length

P. Hoffmann (Czech Republic)


regular inference, machine learning, genetic algorithms


There are known several state merging methods for regu lar language inference from positive and negative samples. One of them is the RPNI algorithm that merges pairs of states of the prefix tree acceptor of the positive samples in a fixed order assuring consistency of the resulting automa ton. The resulting automaton need not be the optimal one. By prohibiting some merges done by the original RPNI al gorithm it is possible to get a better automaton. We propose a new method of searching pairs of states which should not be merged using genetic algorithms and a random walk. The improvement over the original RPNI algorithm is eval uated experimentally.

Important Links:

Go Back