On the gap between separating words and separating their reversals (Q1698731): Difference between revisions

Given two distinct finite words \(x\), \(y\) over the same alphabet and a deterministic finite automaton \(D\), we say that \(D\) \textit{separates} \(x\) and \(y\) if \(D\) accepts the first word but rejects the second. The minimum number of states required for a deterministic finite automaton to separate \(x\) and \(y\) is denoted by \(\operatorname{sep}(x,y)\). In [Lect. Notes Comput. Sci. 6808, 147--157 (2011; Zbl 1341.68087)] \textit{E. D. Demaine} et al. proposed the following open problem: decide whether the difference \[ | \operatorname{sep}(x,y) - \operatorname{sep}(x^R, y^R)| \] is bounded or not, where \(w^R\) stands for the mirror image of a word \(w\). In this paper the author solves the previously open problem showing that the difference is unbounded for alphabets with at least two letters.