Benchmarking State-Merging Algorithms for Learning Regular Languages

Adil Soubki, Jeffrey Heinz
Proceedings of 16th edition of the International Conference on Grammatical Inference, PMLR 217:181-198, 2023.

Abstract

The state-merging algorithms RPNI, EDSM, and ALERGIA are tested on MLRegTest, a benchmark for the learning of regular languages citep{heinz-etal-2022-mlregtest}. MLRegTest contains training, development, and test data for 1,800 regular languages, which themselves are from several well-studied subregular classes. The results show that there is large variation in the performance of these algorithms on the benchmark with EDSM performing the best overall. Furthermore, the mean accuracies on the test data for all three state-merging algorithms are less than the mean accuracies obtained by the neural networks citet{heinz-etal-2022-mlregtest} studied. A further experiment augments the training data in MLRegtest with shorter strings and shows they dramatically improve the performance of the state-merging algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v217-soubki23a, title = {Benchmarking State-Merging Algorithms for Learning Regular Languages}, author = {Soubki, Adil and Heinz, Jeffrey}, booktitle = {Proceedings of 16th edition of the International Conference on Grammatical Inference}, pages = {181--198}, 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/soubki23a/soubki23a.pdf}, url = {https://proceedings.mlr.press/v217/soubki23a.html}, abstract = {The state-merging algorithms RPNI, EDSM, and ALERGIA are tested on MLRegTest, a benchmark for the learning of regular languages citep{heinz-etal-2022-mlregtest}. MLRegTest contains training, development, and test data for 1,800 regular languages, which themselves are from several well-studied subregular classes. The results show that there is large variation in the performance of these algorithms on the benchmark with EDSM performing the best overall. Furthermore, the mean accuracies on the test data for all three state-merging algorithms are less than the mean accuracies obtained by the neural networks citet{heinz-etal-2022-mlregtest} studied. A further experiment augments the training data in MLRegtest with shorter strings and shows they dramatically improve the performance of the state-merging algorithms.} }
Endnote
%0 Conference Paper %T Benchmarking State-Merging Algorithms for Learning Regular Languages %A Adil Soubki %A Jeffrey Heinz %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-soubki23a %I PMLR %P 181--198 %U https://proceedings.mlr.press/v217/soubki23a.html %V 217 %X The state-merging algorithms RPNI, EDSM, and ALERGIA are tested on MLRegTest, a benchmark for the learning of regular languages citep{heinz-etal-2022-mlregtest}. MLRegTest contains training, development, and test data for 1,800 regular languages, which themselves are from several well-studied subregular classes. The results show that there is large variation in the performance of these algorithms on the benchmark with EDSM performing the best overall. Furthermore, the mean accuracies on the test data for all three state-merging algorithms are less than the mean accuracies obtained by the neural networks citet{heinz-etal-2022-mlregtest} studied. A further experiment augments the training data in MLRegtest with shorter strings and shows they dramatically improve the performance of the state-merging algorithms.
APA
Soubki, A. & Heinz, J.. (2023). Benchmarking State-Merging Algorithms for Learning Regular Languages. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217:181-198 Available from https://proceedings.mlr.press/v217/soubki23a.html.

Related Material