A new upper bound for separating words

2020/07/23 by Chase, Zachary
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2007.12097

Abstract

We prove that for any distinct x,y ∈ \0,1\ⁿ, there is a deterministic finite automaton with \widetildeO(n^1/3) states that accepts x but not y. This improves Robson's 1989 upper bound of \widetildeO(n^2/5).

Related

• A Sharper Upper Bound for the Separating Words Problem
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• From regular expressions to deterministic finite automata: 2^(n)/(2)+√(n)(log n)^Θ(1) states are necessary and sufficient
• An improvement to a recent upper bound for synchronizing words of finite automata
• Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?