Springe direkt zu Inhalt

Raphael Walkling:

Separating Words with Small Deterministic Finite Automata


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.

Bachelor of Science (B.Sc.)