NP-Completeness of Finding Minimum Automaton, in Gold's paper
After more and more digging, here is what I found:
First reference: Introduction to Automata Theory, Languages, and Computation 3rd Edition.
Specifically, theorem 4.26 indicates that the provided algorithm constructs a minimum state machine M for a A such that M has as few states as any DFA equivalent to A.
This was my original understanding, so the answer is &quot;NO&quot; to the pre-question.
Second reference: Grammatical Inference: Learning Automata and Grammar
First question:
This book was excellent source for my understanding. It turns out, Gold's construction does not necessarily &quot;EXACTLY&quot; fit the data. The data may be a subset of of the inferred automaton, and this is a key reason as to why eventually, identification in the limit can happen, so ab(ab*)* can be learnt, eventually, but we can never tell we learned it until we wait for ever (I see this as a halting problem sort of issue)
Second question:
The confusion occurred from the meaning of &quot;consistent&quot;. The construction used in the paper has &quot;holes&quot; where an &quot;experiment&quot; is not known to accept or reject a string at that &quot;point in time&quot;. It is difficult to summarize a whole chapter here, but what ends up happening is &quot;consistent&quot; does not mean &quot;EXACT&quot;. Eventually, identification in the limit produces &quot;EXACT&quot; fit for &quot;historical&quot; and &quot;future&quot; experiments.
The reason why identification is NP-Hard is due to the holes in the algorithm. At some point a value is assumed to fill the holes, but based on the value, some inconsistency may arise, and a parsing tree is returned instead (which has large number of states). The other option is to use backtracking to implement nondeterminism and try different values (or run this in parallel...) to find the reduced automaton.
Since the algorithm is non deterministic and can find the correct consistent minimum automaton, finding the minimum automaton from data, in the limit, is NP hard.
Some Final Remarks
If we have a &quot;complete&quot; finite log, we can find the minimum automaton in P.
Then one may ask, what if we generate lots of experiments before we attempt to find an automaton, and assume that the log is complete?
The answer is:
If the log was indeed complete, then an algorithm in P can find the minimum state. Otherwise, the algorithm did not find the minimum state.
I believe this makes the question: &quot;Is the Log Complete?&quot; to be the problem here, because if we can answer that with a YES, then identification of automata from finite data would be possible (not in the limit...), which is not possible.
One way to circumvent this is to add domain knowledge, such as having an upper bound on the number of possible states.