The Regular Expression Inference Challenge
Mojtaba Valizadeh Philip John Gorinski Ignacio Iacobacci Martin Berger
We propose \emph{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 synthesis 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 $\text{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
$\text{cost}(r')<\text{cost}(r)$.
  REI has advantages as a challenge problem: (i) regular expressions are
well-known, widely used, and a natural idealisation of code; (ii) REI's
asymptotic worst-case complexity is well understood; (iii) REI has a small
number of easy to understand parameters (e.g.~$P$ or $N$ cardinality, string
lengths of examples, or the cost function); this lets us easily finetune
REI-hardness; (iv) REI is an unsolved problem for deep learning based ML.
  Recently, an REI solver was implemented on GPUs, using program synthesis
techniques. This enabled, for the first time, fast generation of minimal
expressions for complex REI instances. Building on this advance, we generate
and publish the first large-scale datasets for REI, and devise and evaluate
several initial heuristic and machine learning baselines.
  We invite the community to participate and explore ML methods that learn to
solve REI problems. We believe that progress in REI directly translates to
code/language modelling.