NP-Completeness of Finding Minimum Automaton, in Gold's paper

Question

I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "System Identification Via State Characterization", and I am confused now.

I also checked Is finding the minimum regular expression an NP-complete problem? but I am still confused.

• Let us call Problem 1: Finding a minimum regular expression for a given regular expression which has same language L.

• Let us call Problem 2a: Finding automaton which can explain some data D.

• Let us call Problem 2b: Finding an automaton with minimum states for Problem 2a.

In "Complexity of Automaton.." paper, it states that

"However, it is the objective of this paper to show that the construction of a minimum state 
automaton which agrees with given data is, in general, computationally difficult."

Then later, in Theorem 2:

"Minimum Automaton Identification Question Qmin(D, n). Given: data D,
 positive integer n. Question: Is there a finite automaton with n states which
 agrees with D ?

Now, I can easily create an automaton which fits the data. Lets call it G. I can also minimize G to get G*, and count the number of states.

As I wrote the whole question, I realized that if the answer to the following statement is "NO", then I do need further help. If the answer is "YES", elaboration is appreciated, but a simple yes will clear lots of confusion.

Given arbitrary automaton G for language L, if we use some Polynomial algorithm 
to minimize it to G* (and P =/= NP), can there exist another smaller automaton S < G 
(in number of states) such that language of S is exactly L?

If answer is "NO", please proceed. If the answer is "YES", feel free to elaborate. Any help is appreciated.

First question:

• Gold assumes that a blackbox can be "identified in the limit". However I find that an a regular expression: ab(ab*)* to not apply here, since we don't know the number of states in the FSM we are trying to identify. Hence, this makes me believe Problem 1 is different than Problems 2a and 2b. Correct?

Second question:

• Given the data, I can easily create an automaton, then minimize it. Based on what I've seen (and yet don't understand), the minimal automaton G* is not necessarily the "minimum automaton which can explain the data". There is confusion about what "explain the data" mean. If I minimize G to get G* some known polynomial algorithm, wouldn't that be "Exact" fit for the data? meaning all the data is accepted by G* and G*'s language is only all the data?

Third question:

• Depending on how second question is answered, if there could be another smaller automaton which is difficult to obtain, then that should imply that polynomial minimization algorithms may produce different "minimal" automaton, based either on the algorithm, which I find absurd, or based on the "initial constructed automaton".

I think question 3 is absurd, which is forcing me to believe that Gold meant something specific with "agrees with given data".

Any help is appreciated.

Answer 1

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 "NO" 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 "EXACTLY" 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 "consistent". The construction used in the paper has "holes" where an "experiment" is not known to accept or reject a string at that "point in time". It is difficult to summarize a whole chapter here, but what ends up happening is "consistent" does not mean "EXACT". Eventually, identification in the limit produces "EXACT" fit for "historical" and "future" 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 "complete" 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: "Is the Log Complete?" 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.