IDENTIFYING REGULAR LANGUAGES IN POLYNOMIAL TIME
José Oncina, Pedro García · Series in machine perception and artificial intelligence · 1993
The regular languages are commonly used as models in Syntactical Pattern Recognition tasks. A wide variety of inference algorithms have been developed to learn these models but usually these algorithms only make use of positive information, even though the negative is also available. In this paper we present an algorithm that always obtains a deterministic automaton compatible with the positive and negative data, that can identify in the limit any regular language and works in a polynomial lime. Some experiments are performed to show its behaviour.