Learning random automata using random walks

Gio, 24/03/2022 - 10:00 / 11:00

406AB, Viale Romania

Speaker: Matteo Quattropani , Mathematical Institute of Leiden University


Deterministic Finite Automata (DFAs) are one of the most classical models in theoretical computer science, serving as a building block in the development of the theory of computational learning. It is known that learning all DFAs is computationally intractable. For this reason, in the last decade the learning theory community has made an effort to understand the possibility to design algorithms that efficiently solve the learning problem, at least in the average case. As pointed out by Angluin et al. [1], the average case can be translated into the analysis of a random walk moving on a random DFA. In this talk I will present some recent results on the behaviour of random walks on random DFAs. In particular, I will focus on the meeting time of two independent random walks evolving on the same random DFA and, along the way, I will disprove a recent conjecture by Fish et al. [2].


The results are part of an on-going project with F. Sau (IST Austria).


[1] Angluin, Dana, and Dongqu Chen. "Learning a random DFA from uniform strings and state information." International Conference on Algorithmic Learning Theory. Springer, Cham, 2015.


[2] Fish, Benjamin, and Lev Reyzin. "Open problem: Meeting times for learning random automata." Conference on Learning Theory. PMLR, 2017.