Separating words problem

Unsolved problem in computer science: How many states are needed in a deterministic finite automaton that behaves differently on two given strings of length n? (more unsolved problems in computer science)

In theoretical computer science, the separating words problem is the problem of finding the smallest deterministic finite automaton that behaves differently on two given strings, meaning that it accepts one of the two strings and rejects the other string. It is an open problem how large such an automaton must be, in the worst case, as a function of the length of the input strings.

Example

The two strings 0010 and 1000 may be distinguished from each other by a three-state automaton in which the transitions from the start state go to two different states, both of which are terminal in the sense that subsequent transitions from these two states always return to the same state. The state of this automaton records the first symbol of the input string. If one of the two terminal states is accepting and the other is rejecting, then the automaton will accept only one of the strings 0010 and 1000. However, these two strings cannot be distinguished by any automaton with fewer than three states.^[1]

Simplifying assumptions

For proving bounds on this problem, it may be assumed without loss of generality that the inputs are strings over a two-letter alphabet. For, if two strings over a larger alphabet differ then there exists a string homomorphism that maps them to binary strings of the same length that also differ. Any automaton that distinguishes the binary strings can be translated into an automaton that distinguishes the original strings, without any increase in the number of states.^[1]

It may also be assumed that the two strings have equal length. For strings of unequal length, there always exists a prime number p whose value is logarithmic in the smaller of the two input lengths, such that the two lengths are different modulo p. An automaton that counts the length of its input modulo p can be used to distinguish the two strings from each other in this case. Therefore, strings of unequal lengths can always be distinguished from each other by automata with few states.^[1]

History and bounds

The problem of bounding the size of an automaton that distinguishes two given strings was first formulated by Goralčík & Koubek (1986), who showed that the automaton size is always sublinear.^[2] Later, Robson (1989) proved the best upper bound known, O(n^2/5(log n)^3/5), on the automaton size that may be required.^[3]

There exist pairs of inputs that are both binary strings of length n for which any automaton that distinguishes the inputs must have size Ω(log n). Closing the gap between this lower bound and Robson's upper bound remains an open problem.^[1] Jeffrey Shallit has offered a prize of 100 British pounds for any improvement to Robson's upper bound.^[4]

Special cases

Several special cases of the separating words problem are known to be solvable using few states:

• If two binary words have differing numbers of zeros or ones, then they can be distinguished from each other by counting their Hamming weights modulo a prime of logarithmic size, using a logarithmic number of states. More generally, if a pattern of length k appears a different number of times in the two words, they can be distinguished from each other using O(k log n) states.^[1]
• If two binary words differ from each other within their first or last k positions, they can be distinguished from each other using k + O(1) states. This implies that almost all pairs of binary words can be distinguished from each other with a logarithmic number of states, because only a polynomially small fraction of pairs have no difference in their initial O(log n) positions.^[1]
• If two binary words have Hamming distance d, then there exists a prime p with p = O(d log n) and a position i at which the two strings differ, such that i is not equal modulo p to the position of any other difference. By computing the parity of the input symbols at positions congruent to i modulo p, it is possible to distinguish the words using an automaton with O(d log n) states.^[1]

References

1. Demaine, Erik D.; Eisenstat, Sarah; Shallit, Jeffrey; Wilson, David A. (2011), "Remarks on separating words", Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011, Proceedings, Lecture Notes in Computer Science, 6808, Heidelberg: Springer-Verlag, pp. 147–157, arXiv:1103.4513, doi:10.1007/978-3-642-22600-7_12, MR 2910373.
2. Goralčík, P.; Koubek, V. (1986), "On discerning words by automata", Automata, Languages and Programming: 13th International Colloquium, Rennes, France, July 15–19, 1986, Proceedings, Lecture Notes in Computer Science, 226, Berlin: Springer-Verlag, pp. 116–122, doi:10.1007/3-540-16761-7_61, MR 864674.
3. Robson, J. M. (1989), "Separating strings with small automata", Information Processing Letters, 30 (4): 209–214, doi:10.1016/0020-0190(89)90215-9, MR 986823.
4. Shallit, Jeffrey (2014), "Open Problems in Automata Theory: An Idiosyncratic View", British Colloquium for Theoretical Computer Science (BCTCS 2014), Loughborough University (PDF).