[edit]

# Open Problem: Meeting Times for Learning Random Automata

*Proceedings of the 2017 Conference on Learning Theory*, PMLR 65:8-11, 2017.

#### Abstract

Learning automata is a foundational problem in computational learning theory. However, even efficiently learning random DFAs is hard. A natural restriction of this problem is to consider learning random DFAs under the uniform distribution. To date, this problem has no non-trivial lower bounds nor algorithms faster than brute force. In this note, we propose a method to find faster algorithms for this problem. We reduce the learning problem to a conjecture about meeting times of random walks over random DFAs, which may be of independent interest to prove.