Supervisor

Suitable for

Abstract

Let A be a non-deterministic finite automaton (NFA) with n states. Such automaton is called unambiguous if for every word w and every pair p, q of its states, the number of paths from p to q labelled by w is at most one (sometimes such automata are called diamond-free). A word w is called mortal for A if for every state q there is no path starting in q and labelled by w. In https://arxiv.org/abs/1808.00940, Kiefer and Mascle proved that if an unambiguous NFA admits a mortal word, then the length of a shortest such word is at most n^5. However, the best known lower bound for this value is quadratic in n.

The experimental part of the project is to perform an exhaustive search for small unambiguous NFAs, and come up with a conjecture of how this upper bound should actually look like. This is challenging, because even for small n the number of NFAs is very large, and finding the length of a shortest mortal word is hard, but there are some good existing approaches to deal with that (for example, https://arxiv.org/abs/2207.05495).

The theoretical part is to try to improve the lower or the upper bound for this question, ideally using the examples obtained from the experimental part. As an intermediate step for that, we will look at restricted cases, especially at unambiguous NFAs associated to finite prefix codes (also known as Huffman codes) and special classes of Boolean matrices.

Prerequisites: good familiarity with discrete mathematics, algorithms and linear algebra (for both theoretical and experimental parts), ability to design and implement non-trivial algorithms in a programming language of your choice (for the experimental part)