A new regular language learning algorithm from lexicographically ordered complete samples

A regular language learning algorithm is presented to obtain descriptions which consist of deterministic finite automata (DFAs). The process is an identification in the limit process. The main characteristic is that the DFAs are conjectured using a constructive strategy which does not use a large data space. The total time used is polynomial in the size of the minimum-state DFA and the data seen so far. In the course of learning, the algorithm uses deterministic hypotheses which are bounded in space with the minimal state DFA, consistent with the sample and the single sample string used as input. The algorithm works on lexicographically ordered samples and this order is shown to be transcendental for learning.