Separating strings with small automata (Q1116698): Difference between revisions

A finite deterministic complete automaton separates a pair u, v of input words if the actions of u and v are different. A problem arises of bounds for the function Sep(n) defined as the minimal number k of states such that for any pair, u, v of words of length at most n over a finite alphabet A one can produce a k-state automaton separating the pair. The paper brings the best yet known upper bound, to wit, \(Sep(n)=O(n^{2/5} \log^{3/5} n)\). The author regards the estimate \(O(n^{\epsilon})\) for any positive \(\epsilon\), conjectured by Ch. Choffrut, as unlikely.