Proceedings

ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

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

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 3908-3916.

https://doi.org/10.24963/ijcai.2026/435

Keywords

  • Knowledge Representation and Reasoning: Knowledge representation languages
  • Knowledge Representation and Reasoning: Computational complexity of reasoning
  • Knowledge Representation and Reasoning: Learning and reasoning
  • Knowledge Representation and Reasoning: Automated reasoning and theorem proving

Abstract

Existing Programming-By-Example (PBE) systems often rely on simplified benchmarks that fail to capture the high structural complexity of real-world regexes, such as deeper nesting and frequent use of union operations.

To overcome the resulting performance drop, we propose ReSyn, a synthesizer-agnostic divide-and-conquer framework that decomposes complex synthesis problem 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.

Seongmin Kim, Hyunjoon Cheon, Su-Hyeon Kim, Yo-Sub Han, and Sang-Ki Ko. 2026. ReSyn: A Generalized Recursive Regular Expression Synthesis Framework. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 3908–3916. https://doi.org/10.24963/ijcai.2026/435
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards