ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

Seongmin Kim; Hyunjoon Cheon; Su-Hyeon Kim; Yo-Sub Han; Sang-Ki Ko

IJCAI 20260 citations

ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

Seongmin Kim, Hyunjoon Cheon, Su-Hyeon Kim, Yo-Sub Han, Sang-Ki Ko

Abstract

Existing Programming-By-Example (PBE) systems often rely on simplified benchmarks that fail to capture the high structural complexity—such as deeper nesting and frequent Unions—of real-world regexes. To overcome the resulting performance drop, we propose ReSyn, a synthesizer-agnostic divide-and-conquer framework that decomposes complex synthesis problems into manageable sub-problems. We also introduce Set2Regex, a parameter-efficient synthesizer capturing the permutation invariance of examples. Experimental results demonstrate that ReSyn significantly boosts accuracy across various synthesizers, and its combination with Set2Regex establishes a new state-of-the-art on challenging real-world benchmark. The complete source code, datasets, and pre-trained model checkpoints are publicly available at https://github.com/mrseongminkim/ReSyn.

Knowledge Representation and Reasoning: Automated reasoning and theorem provingKnowledge Representation and Reasoning: Computational complexity of reasoningKnowledge Representation and Reasoning: Knowledge representation languagesKnowledge Representation and Reasoning: Learning and reasoning

BibTeX

@inproceedings{ijcai2026_resynageneralize,
  title = {ReSyn: A Generalized Recursive Regular Expression Synthesis Framework},
  author = {Seongmin Kim and Hyunjoon Cheon and Su-Hyeon Kim and Yo-Sub Han and Sang-Ki Ko},
  booktitle = {IJCAI 2026},
  year = {2026}
}