On the Hardness of Learning Regular Expressions

Idan Attias, Lev Reyzin, Nathan Srebro, Gal Vardi
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-19, 2026.

Abstract

Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-attias26a, title = {On the Hardness of Learning Regular Expressions}, author = {Attias, Idan and Reyzin, Lev and Srebro, Nathan and Vardi, Gal}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--19}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/attias26a/attias26a.pdf}, url = {https://proceedings.mlr.press/v313/attias26a.html}, abstract = {Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.} }
Endnote
%0 Conference Paper %T On the Hardness of Learning Regular Expressions %A Idan Attias %A Lev Reyzin %A Nathan Srebro %A Gal Vardi %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-attias26a %I PMLR %P 1--19 %U https://proceedings.mlr.press/v313/attias26a.html %V 313 %X Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.
APA
Attias, I., Reyzin, L., Srebro, N. & Vardi, G.. (2026). On the Hardness of Learning Regular Expressions. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-19 Available from https://proceedings.mlr.press/v313/attias26a.html.

Related Material