[edit]

# Lower Bounds for Active Automata Learning

*Proceedings of 16th edition of the International Conference on Grammatical Inference*, PMLR 217:157-180, 2023.

#### Abstract

We study lower bounds for the number of output and equivalence queries required for active learning of finite state machines, with a focus on $L^{#}$, a new learning algorithm that requires fewer queries for learning than other state-of-the-art algorithms on a large collection of benchmarks. We improve the lower bound of cite{BalcazarDG97} on the combined number of output and equivalence queries required by any learning algorithm, and give a simpler proof. We prove that in the worst case $L^{#}$ needs $n-1$ equivalence queries to learn an FSM with $n$ states, and establish lower bounds on the number of output queries needed by $L^{#}$ in the worst case. In practical applications, the maximum length of the shortest separating sequence for all pairs of inequivalent states (MS3) is often just $1$ or $2$. We present $L^{#}_h$, a version of $L^{#}$ with bounded lookahead $h$, which learns FSMs with an MS3 of at most $h$ without requiring any equivalence queries, and give lower and upper bounds on its complexity.