2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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" book by Colin de La Higuera.

$\endgroup$
  • $\begingroup$ Also, Mark Gold proved that finding the minimal automaton consistent with a set of positive examples is NP hard. $\endgroup$ – Roman Manevich Feb 12 at 19:49
  • $\begingroup$ 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. $\endgroup$ – Roman Manevich Feb 12 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.