Correct and Optimal: the Regular Expression Inference Challenge
Mojtaba Valizadeh, Philip John Gorinski, Ignacio Iacobacci, Martin Berger · arXiv (Cornell University) · 2023
We propose regular expression inference (REI) as a challenge for code/language modelling, and the wider machine learning community. REI is a supervised machine learning (ML) and program optimisation task, and poses the problem of finding minimal regular expressions from examples: Given two finite sets of strings $P$ and $N$ and a cost function $cost(\cdot)$, the task is to generate an expression $r$ that accepts all strings in $P$ and rejects all strings in $N$, while no other such expression $r'$ exists with $cost(r')