Publication at Faculty of Mathematics and Physics |
2007
Abstract
There are known several state merging methods for regular 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 automaton.
The resulting automaton need not be the optimal one. By prohibiting some merges done by the original RPNI algorithm 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 evaluated experimentally.