A new upper bound for separating words

Abstract: We prove that for any distinct

x, y i n {0, 1}^{n}

, there is a deterministic finite automaton with

w i d e t i l d e O (n^{1 / 3})

states that accepts

x

but not

y

. This improves Robson's 1989 upper bound of

w i d e t i l d e O (n^{2 / 5})

.

This page was built for publication: A new upper bound for separating words