On the Gap Between Separating Words and Separating Their Reversals

Farzam Ebrahimnejad

doi:10.1016/j.tcs.2017.11.012

paper

On the Gap Between Separating Words and Separating Their Reversals

arXiv:1605.04835 · doi:10.1016/j.tcs.2017.11.012

Abstract

A deterministic finite automaton (DFA) separates two strings $w$ and $x$ if it accepts $w$ and rejects $x$ . The minimum number of states required for a DFA to separate $w$ and $x$ is denoted by $se p (w, x)$ . The present paper shows that the difference $∣ se p (w, x) - se p (w^{R}, x^{R}) ∣$ is unbounded for a binary alphabet; here $w^{R}$ stands for the mirror image of $w$ . This solves an open problem stated in [Demaine, Eisenstat, Shallit, Wilson: Remarks on separating words. DCFS 2011. LNCS vol. 6808, pp. 147-157.]

22 pages, 2 figures

References in corpus (1)

Remarks on separating words