11
$\begingroup$

There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, meaning accept one string but reject the other.

Here are some relevant papers 1, 2. (I have a few more but I don't have enough reputation to post them).

These all discuss the problem of separating two distinct strings. I am wondering if there been any work done in the area of separating lists of strings, meaning given two lists of strings, $A$ and $B$, what size DFA is required to accept every string in $A$ and reject every string in $B$. This problem is equivalent to regex golf.

There are some basic questions that I have been working on such as if one of the lists is of size $1$ or if all the strings are of different lengths.

I have been searching around but haven't found any papers that deal with this type of problem. Has there been any research done in this area?

Thanks in advance.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ fyi same as minimal DFA given in-words & out-words $\endgroup$
    – vzn
    Apr 16, 2015 at 2:09
  • $\begingroup$ VZN's link is great! However, I believe you can find even more info if you take a look in the appendix of: "Computers and Intractability: A Guide to the Theory of NP-Completeness" $\endgroup$
    – Michael Wehar
    Apr 20, 2015 at 1:23
  • $\begingroup$ Also, if you're interested in separating two lists with a linear time bounded Turing machines, I gave a little construction and posted the write-up online (it's nothing that special). Basically, for two k element lists where each string has length at most n, you can separate the lists with a Turing machine that has $k\frac{log(n)}{log(log(n))}$ states and has an "optimal runtime". $\endgroup$
    – Michael Wehar
    Apr 20, 2015 at 1:26
  • 1
    $\begingroup$ By Gold1978, we know that the problem of determining if two lists can be separated by a DFA of a given size is NP-complete. If you modify the problem to say separated by a Turing machine with a time bound written in unary, then it's not known if the problem is NP-complete. It's been suggested that this problem may be related to the minimum circuit problem in which case it would resolve open problems in structural complexity if you showed it was in P or if it was NP-complete. $\endgroup$
    – Michael Wehar
    Apr 20, 2015 at 1:36
  • 1
    $\begingroup$ Possible duplicate of Is finding the minimum regular expression an NP-complete problem? $\endgroup$
    – Boson
    Feb 3, 2016 at 8:29

2 Answers 2

Reset to default
9
$\begingroup$

The question you are asking is known as the separation problem for languages: Given two languages $K$ and $L$, is there a third language $M$ (a separator) that separates them, i.e. $K \subseteq M$ and $M \cap L = \emptyset$.

You are interested in the restricted case where $K$ and $L$ are finite, and in the size of a DFA for $M$.

In a 2013 paper, authors indicate:

Although the separation problem frequently occurs, it has however not been systematically studied, even in the restricted, yet still challenging case of regular languages.

They however mention several special cases that have been solved, and that most certainly encompass the finite case.

You may also want to look at Craig interpolant, a similar problem on logical formulae. Interpolation is used for instance in SAT-based model-checking, in a setting which I think is closer to what you are looking for (especially regarding finiteness of the input). This paper should be a good starting point.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I appreciate that you shared this. I didn't know about this paper. Thank you. :) $\endgroup$
    – Michael Wehar
    Apr 20, 2015 at 1:56
3
$\begingroup$

The special case of having exactly one word in $A$ and one word in $B$ has been mentioned here before.

This is called the "The Separating Words Problem". The slides by Shallit pretty much cover all that is known about the problem (see slides1 and slides2).

Improve this answer
$\endgroup$
1

Your Answer

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

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