ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

• URL: http://arxiv.org/abs/2603.24624v1
• Date: Wed, 25 Mar 2026 01:29:42 GMT
• Title: ReSyn: A Generalized Recursive Regular Expression Synthesis Framework
• Abstract summary: We propose ReSyn, a synthesizer-a divide-and-conquer framework that decomposes complex synthesis problems into manageable sub-problems.<n>We also introduce Set2Regex, a parameter-efficient synthesizer capturing the permutation invariance of examples.
• Score: 8.58401487492519
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Natural Synthesis: Outperforming Reactive Synthesis Tools with Large Reasoning Models [7.768952514701895]
  Reactive synthesis is the problem of automatically constructing a hardware circuit from a logical specification.<n>We present a neuro-symbolic approach to reactive synthesis that couples large reasoning models with model checkers.<n>On the specification side, we introduce an autoformalization step that shifts the specification task from temporal logic to natural language.
  arXiv  Detail & Related papers  (2026-05-14T17:39:58Z)
• FePySR: A Neural Feature Extraction Framework for Efficient and Scalable Symbolic Regression [4.327979408469824]
  We introduce FePySR, a two-stage framework that reduces the SR search space by extracting valid features prior to equation search.<n>Across five standard benchmarks, FePySR outperforms state-of-the-art methods by achieving higher equation recovery rates.<n>FePySR is a generalizable framework that can enhance the SR solvers, enabling the efficient and reliable recovery of symbolic expressions.
  arXiv  Detail & Related papers  (2026-05-12T20:04:59Z)
• High-Performance Exact Synthesis of Two-Qubit Quantum Circuits [0.0]
  We present an exact synthesis framework for two-qubit circuits over the Clifford+$T$ gate set.<n>Our approach exhausts a bounded search space, exploits algebraic canonicalization to avoid redundancy, and constructs a lookup table of optimal implementations that turns synthesis into a query.
  arXiv  Detail & Related papers  (2026-01-27T03:57:04Z)
• Randomized Benchmarking with Synthetic Quantum Circuits [0.471858286267785]
  We introduce a broad framework for enhancing the sample efficiency of Randomized benchmarking (RB)<n>Our strategy, which applies to any benchmarking group, uses "synthetic" quantum circuits with classical post-processing of both input and output data.<n>We show that, for experimentally accessible high-spin systems, synthetic RB protocols can reduce the complexity of measuring rotationally invariant error rates.
  arXiv  Detail & Related papers  (2024-12-24T18:10:00Z)
• SynthesizRR: Generating Diverse Datasets with Retrieval Augmentation [55.2480439325792]
  We study the synthesis of six datasets, covering topic classification, sentiment analysis, tone detection, and humor. We find that SynthesizRR greatly improves lexical and semantic diversity, similarity to human-written text, and distillation performance.
  arXiv  Detail & Related papers  (2024-05-16T12:22:41Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• Compositional Generalization and Decomposition in Neural Program Synthesis [59.356261137313275]
  In this paper, we focus on measuring the ability of learned program synthesizers to compositionally generalize. We first characterize several different axes along which program synthesis methods would be desired to generalize. We introduce a benchmark suite of tasks to assess these abilities based on two popular existing datasets.
  arXiv  Detail & Related papers  (2022-04-07T22:16:05Z)
• SRU++: Pioneering Fast Recurrence with Attention for Speech Recognition [49.42625022146008]
  We present the advantages of applying SRU++ in ASR tasks by comparing with Conformer across multiple ASR benchmarks. Specifically, SRU++ can surpass Conformer on long-form speech input with a large margin, based on our analysis.
  arXiv  Detail & Related papers  (2021-10-11T19:23:50Z)
• Finding needles in a haystack: Sampling Structurally-diverse Training Sets from Synthetic Data for Compositional Generalization [33.30539396439008]
  We investigate automatic generation of synthetic utterance-program pairs for improving compositional generalization in semantic parsing. We select a subset of synthetic examples that are structurally-diverse and use them to improve compositional generalization. We evaluate our approach on a new split of the schema2QA dataset, and show that it leads to dramatic improvements in compositional generalization as well as moderate improvements in the traditional i.i.d setup.
  arXiv  Detail & Related papers  (2021-09-06T16:20:47Z)
• Syntactic representation learning for neural network based TTS with syntactic parse tree traversal [49.05471750563229]
  We propose a syntactic representation learning method based on syntactic parse tree to automatically utilize the syntactic structure information. Experimental results demonstrate the effectiveness of our proposed approach. For sentences with multiple syntactic parse trees, prosodic differences can be clearly perceived from the synthesized speeches.
  arXiv  Detail & Related papers  (2020-12-13T05:52:07Z)
• Synthesizer: Rethinking Self-Attention in Transformer Models [93.08171885200922]
  dot product self-attention is central and indispensable to state-of-the-art Transformer models. This paper investigates the true importance and contribution of the dot product-based self-attention mechanism on the performance of Transformer models.
  arXiv  Detail & Related papers  (2020-05-02T08:16:19Z)
• Multi-level Head-wise Match and Aggregation in Transformer for Textual Sequence Matching [87.97265483696613]
  We propose a new approach to sequence pair matching with Transformer, by learning head-wise matching representations on multiple levels. Experiments show that our proposed approach can achieve new state-of-the-art performance on multiple tasks.
  arXiv  Detail & Related papers  (2020-01-20T20:02:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.