Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y. One way to do this is brute force search. You enumerate DFA's starting with the smallest. You try each DFA until you find one that accepts x and rejects y.
I want to know if there is any other known way of finding or building a minimum size DFA that accepts x and rejects y. In other words, can we beat brute force search?
Additional infoMore Detail:
(1) I really do want an algorithm to find a minimum size DFA, not a near minimum size DFA.
(2) I don't just want to know how large or small the minimum DFA is.
(3) Right here, I'm only focused on the case were you have two strings x and y.
Edit:
Additional information for the interested reader:
Suppose $x$ and $y$ are binary strings of length at most $n$. It is a known result that there is a DFA that accepts $x$ and rejects $y$ with at most $\sqrt{n}$ states. Notice that there are about $n^{\sqrt{n}}$ DFA's with a binary alphabet and at most $\sqrt{n}$ states. Therefore, the brute force approach wouldn't require us to enumerate through more than $n^{\sqrt{n}}$ DFA's. It follows that the brute force approach couldn't take much more than $n^{\sqrt{n}}$ time.
Slides that I found helpful: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf