Here it is a short nonrestrictive list of some concrete topics to be developed in a master / PhD thesis project.
More topics will be proposed as mini-research projects.
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.