4
$\begingroup$

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight.

given: two finite sets of words $S_{in}$ and $S_{out}$. find the smallest FSM with language $L$ such that for each $x \in S_{in}$, $x \in L$ and for each $y \in S_{out}$, $y \notin L$.

in other words one is given finite lists of words that are in the language and not in the language. there is a simple algorithm of creating an FSM with the given (non)acceptance and then minimizing it, but is this also the smallest possible? it seems to come down some to the question of cycles in the FSM graph. the simple strategy will not have cycles, so could smaller FSMs with cycles exist? there is also the question of nondeterminism.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 1. You might be interested in Is regex golf NP-Complete?. It's not exactly the same thing, but it's related (it's for regexes rather than DFA). 2. Please specify precisely what you mean by a FSM. Do you mean a DFA? or a NFA? $\endgroup$
    – D.W.
    Commented Dec 27, 2014 at 0:53
  • 3
    $\begingroup$ I think this is an extension of the problem of separating strings with automata. $\endgroup$
    – Shaull
    Commented Dec 27, 2014 at 13:33
  • $\begingroup$ it is known computing minimal NFAs is rather difficult. am ok with partial answer(s) that focus on the simpler DFA case. also there are interesting natural lower bounds/ "compressibility" questions that some word sets are "harder" than others ie lead to (much?) more states than others. $\endgroup$
    – vzn
    Commented Dec 28, 2014 at 2:34
  • 1
    $\begingroup$ I'm quite interested in these three problems. Please feel free to contact me if you are too. (1) Minimum PDA given in-words and out-words. (2) Minimum DFA given 1 in-word and 1 out-word. (3) Minimum Turing machine given time bound and in-words and out-words. Thanks! $\endgroup$
    – Michael Wehar
    Commented Jan 5, 2015 at 16:36
  • $\begingroup$ realized this may be somewhat connected to Hidden Markov models theory. eg in this recent paper Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets Paulson/ Griffin $\endgroup$
    – vzn
    Commented Jan 7, 2015 at 16:09

1 Answer 1

Reset to default
8
$\begingroup$

If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete

Gold1978 - Complexity of Automaton Identification from Given Data.

The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of states is an approximation of the number of states of a minimum consistent DFA.

Pitt-Warmuth-1993 - The minimum consistent DFA problem cannot be approximated within any polynomial.

There are many known heuristics and algorithms for tackling this problems. A well studied algorithm is due to Angluin.

Angluin-1987 - Learning regular sets from queries and counterexamples

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The key point to note is that a DFA accepting the positive instances and nothing else (which can be constructed, via the Myhill-Nerode theorem, in polynomial time) may be much larger than a DFA that accepts some superset of the positive instances, but still doesn't accept any of the negative instances. Intuitively, this problem is hard because the search is over the exponential sized collection of supersets of the positive instances that are also subsets of the complement of the negative instances. $\endgroup$
    – András Salamon
    Commented Dec 31, 2014 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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