Lower Bounds for Active Automata Learning

Loes Kruger, Bharat Garhewal, Frits Vaandrager
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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v217-kruger23a, title = {Lower Bounds for Active Automata Learning}, author = {Kruger, Loes and Garhewal, Bharat and Vaandrager, Frits}, booktitle = {Proceedings of 16th edition of the International Conference on Grammatical Inference}, pages = {157--180}, year = {2023}, editor = {Coste, François and Ouardi, Faissal and Rabusseau, Guillaume}, volume = {217}, series = {Proceedings of Machine Learning Research}, month = {10--13 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v217/kruger23a/kruger23a.pdf}, url = {https://proceedings.mlr.press/v217/kruger23a.html}, 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.} }
Endnote
%0 Conference Paper %T Lower Bounds for Active Automata Learning %A Loes Kruger %A Bharat Garhewal %A Frits Vaandrager %B Proceedings of 16th edition of the International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2023 %E François Coste %E Faissal Ouardi %E Guillaume Rabusseau %F pmlr-v217-kruger23a %I PMLR %P 157--180 %U https://proceedings.mlr.press/v217/kruger23a.html %V 217 %X 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.
APA
Kruger, L., Garhewal, B. & Vaandrager, F.. (2023). Lower Bounds for Active Automata Learning. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217:157-180 Available from https://proceedings.mlr.press/v217/kruger23a.html.

Related Material