A Sharper Upper Bound for the Separating Words Problem

2025/03/29 by Dumitru, Bogdan C.
#FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2503.23184

Abstract

We show that for any two distinct words s₁, s₂ over an arbitrary alphabets, there exists a deterministic finite automaton with O(log² n) states that accepts s₁ and rejects s₂ . This improves the previous upper bound of O(n^1/3log⁷ n)

Related

• A new upper bound for separating words
• Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?
• From regular expressions to deterministic finite automata: 2^(n)/(2)+√(n)(log n)^Θ(1) states are necessary and sufficient
• Finite automata and pattern avoidance in words
• Remarks on separating words