# Oncina-Garcia RPNI algorithm for learning DFAs

The question refers to this paper: ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf

Given a sample of $$p$$ positive and $$n$$ negative strings, RPNI constructs a consistent DFA in time $$O((p+n)p^2)$$. Nothing is claimed about the size of this DFA; if its size were $$o((p+n)/\log(p+n)))$$, that would imply a compression-based generalization bound. Of course, if they were able to always compress to size poly(opt) -- where opt is the size of the minimal consistent DFA --- that would imply P=NP, via a result of Pitt and Warmuth.

Questions: (1) Is anything at all known about the size of RNPI's resulting DFA? (2) In the linked paper, they claim that RNPI "can identify any regular language in the limit". Has that claim been rigorously proved anywhere? I couldn't find such a proof in the paper.