Raphael Walkling:
Separating Words with Small Deterministic Finite Automata
Kurzbeschreibung
The separating words problem poses the question of how many states a deterministic finite automaton needs to have in order to distinguish two given strings, with respect to their length n. We aim to provide an easily accessible version of the algorithms and proofs given in J. M. Robson's 1989 Paper "Separating Strings with Small Automata", which established an upper bound on the state count of O(n^{2/5} log^{3/5}{n}), which had not seen any improvements until earlier this year.