Here it is a short nonrestrictive list of some concrete topics to be developed in a master / PhD thesis project.
I'm also open to interesting suggestions!
More topics can be found in the automata theory master seminar.
I have some funding for supporting a MSc candidate. Contact me if you are interested.
I'm looking for a PhD candidate. Contact me if you are interested
Show that zeroness / equivalence of power series defined with algebraic differential equations can be decided with elementary complexity.
Prove / disprove the following conjecture: Zeroness / equivalence of polynomial recursive sequences can be decided with elementary complexity [1, 2].
Define a natural class of power series simultaneously generalising D-finite power series and constructible differentially algebraic power series [1, 2].
Show that zeroness / equivalence of weighted VASS over a 1-letter alphabet is decidable (undecidable for large alphabets).
Show that zeroness / equivalence of weighted Parikh automata is decidable.
Show that zeroness / equivalence of weighted 1-counter automata is decidable (cf. recent progress in a restricted setting).
Decide whether two data languages recognised by nondeterministic register automata are separable by some data language recognised by a deterministic register automaton.
Decide whether two timed languages recognised by nondeterministic timed automata are separable by some timed language recognised by a deterministic timed automaton.
Prove/disprove the following conjecture: 1-register non-deterministic automata are always separable by a deterministic one.
Algorithms manipulating nondeterministic finite automata (NFA) usually run faster on smaller instances. For this reason, the problem of reducing the size of NFA has received a lot of attention. One popular approach quotients the state space automaton w.r.t. suitable efficiently computable equivalence relations, such a simulation relations [1]. Another sound equivalence is multiplicity equivalence (is it the case that for every word the two states have the same number of accepting runs?). It can be computed in PTIME using linear algebra, however exploiting it in state space reduction has not been done so far. The aim of this project is to combine simulation and multiplicity equivalence relations to improve the state of the art in state space reduction for NFA.