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.

提出正则表达式推理（REI）作为代码/语言模拟的挑战，并对更广泛的机器学习社区提出。REI是一项监督式机器学习和程序综合任务，通过示例来找到最小的正则表达式。最近在GPU上实现了REI求解器，首次实现了用于复杂REI实例的快速最小表达式生成。以此为基础，我们生成并发布了REI的第一个大规模数据集，并设计和评估了几种初始启发式和机器学习基准方法。邀请社区参与并探索学习解决REI问题的机器学习方法。我们相信，在REI方面的进展直接转化为代码/语言模型。

正则表达式推理挑战