<p>The algorithm is named RPNI, not RNPI.</p>

<p>Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., minimal) DFA for that language. If the generating language is not regular, the automaton may grow unboundedly with the set of inputs.</p>

<p>Since the algorithm merges states, the output automaton has at most |p| states. Therefore, the output is bounded by the sum of input lengths in p.</p>

<p>A proof appears in "Inferring regular languages in polynomial update time".
There are more details about the algorithm in the "<a href="https://www.cambridge.org/core/books/grammatical-inference/CEEB229AC5A80DFC6436D860AC79434F" rel="noreferrer">Grammatical Inference</a>" book by Colin de La Higuera.</p>

CC BY-SA 4.0
2019-02-12T19:49:58.433Z
Also, Mark Gold proved that finding the minimal automaton consistent with a set of positive examples is NP hard.
Roman Manevich
CC BY-SA 4.0
2019-02-12T20:39:02.630Z
More precisely, once a set of examples includes a characteristic set (roughly, a lexicographically-shortest word that reaches every state in the canonical automaton and a negative example that contains a suffix separating every pair of states in the canonical automaton), the output is the canonical automaton.
Roman Manevich
CC BY-SA 4.0
2019-02-12T18:23:39.360Z
2019-02-12T19:48:07.843Z
2019-02-12T19:48:07.843Z
Roman Manevich
<p>The question refers to this paper:
<a href="ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf" rel="nofollow noreferrer">ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf</a></p>

<p>Given a sample of <span class="math-container">$p$</span> positive and <span class="math-container">$n$</span> negative strings, RPNI constructs a consistent DFA in time <span class="math-container">$O((p+n)p^2)$</span>. Nothing is claimed about the size of this DFA; if its size were <span class="math-container">$o((p+n)/\log(p+n)))$</span>, 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.</p>

<p>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.</p>

<machine-learning><lg.learning><regular-language><dfa>
Oncina-Garcia RPNI algorithm for learning DFAs
Aryeh
# Oncina-Garcia RPNI algorithm for learning DFAs

(Asked by: username_0 on 2019-02-12)

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.

**Tags:** machine-learning, lg.learning, regular-language, dfa

---

## 1 answers

### Answer by username_1 on 2019-02-12. Score: 5 | Accepted answer

The algorithm is named RPNI, not RNPI.

Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., minimal) DFA for that language. If the generating language is not regular, the automaton may grow unboundedly with the set of inputs.

Since the algorithm merges states, the output automaton has at most |p| states. Therefore, the output is bounded by the sum of input lengths in p.

A proof appears in "Inferring regular languages in polynomial update time".
There are more details about the algorithm in the "[Grammatical Inference](https://www.cambridge.org/core/books/grammatical-inference/CEEB229AC5A80DFC6436D860AC79434F)" book by Colin de La Higuera.

> **Comments:**
> **username_1**: Also, Mark Gold proved that finding the minimal automaton consistent with a set of positive examples is NP hard.  
> **username_1**: More precisely, once a set of examples includes a characteristic set (roughly, a lexicographically-shortest word that reaches every state in the canonical automaton and a negative example that contains a suffix separating every pair of states in the canonical automaton), the output is the canonical automaton.  

---

