Springe direkt zu Inhalt

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.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
12.01.2021