On Synthesis of Timed Regular Expressions

• URL: http://arxiv.org/abs/2509.06262v2
• Date: Thu, 11 Sep 2025 02:14:56 GMT
• Title: On Synthesis of Timed Regular Expressions
• Authors: Ziran Wang, Jie An, Naijun Zhan, Miaomiao Zhang, Zhenya Zhang,
• Abstract summary: Timed regular expressions serve as a formalism for specifying real-time behaviors of Cyber-Physical Systems.<n>In this paper, we consider the synthesis of timed regular expressions, focusing on generating a timed regular expression consistent with a given set of system behaviors.
• Score: 8.729947740812237
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Timed regular expressions serve as a formalism for specifying real-time behaviors of Cyber-Physical Systems. In this paper, we consider the synthesis of timed regular expressions, focusing on generating a timed regular expression consistent with a given set of system behaviors including positive and negative examples, i.e., accepting all positive examples and rejecting all negative examples. We first prove the decidability of the synthesis problem through an exploration of simple timed regular expressions. Subsequently, we propose our method of generating a consistent timed regular expression with minimal length, which unfolds in two steps. The first step is to enumerate and prune candidate parametric timed regular expressions. In the second step, we encode the requirement that a candidate generated by the first step is consistent with the given set into a Satisfiability Modulo Theories (SMT) formula, which is consequently solved to determine a solution to parametric time constraints. Finally, we evaluate our approach on benchmarks, including randomly generated behaviors from target timed models and a case study.

Related papers

• Extracting Explainable Dates From Medical Images By Reverse-Engineering UNIX Timestamps [0.0]
  We show that regular expressions can be created through regular expression synthesis to identify complex dates and date ranges in text transcriptions.<n>To our knowledge, our proposed way of learning deterministic logic by reverse-engineering several many-one mappings and feeding these into a regular expression synthesiser is a new approach.
  arXiv  Detail & Related papers  (2025-05-16T17:07:14Z)
• Real-time Regular Expression Matching [65.268245109828]
  This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem. This paper presents a theoretical and hardware solution to the exponential blow-up problem for some complicated classes of regular languages.
  arXiv  Detail & Related papers  (2023-08-20T09:25:40Z)
• Euclidean time method in Generalized Eigenvalue Equation [0.0]
  We develop the Euclidean time method of the variational quantum eigensolver for solving the generalized eigenvalue equation $A ketphi_n.
  arXiv  Detail & Related papers  (2023-07-27T06:20:12Z)
• A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
  We propose a hybrid system capable of solving arithmetic problems that require compositional and systematic reasoning over sequences of symbols. We show that the proposed system can accurately solve nested arithmetical expressions even when trained only on a subset including the simplest cases.
  arXiv  Detail & Related papers  (2023-06-29T18:35:41Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  We provide the first type-I-error and expected-rejection-time guarantees under general non-data generating processes. We show how to apply our results to inference on parameters defined by estimating equations, such as average treatment effects.
  arXiv  Detail & Related papers  (2022-12-29T18:37:08Z)
• Time Dependent Hamiltonian Simulation Using Discrete Clock Constructions [42.3779227963298]
  We provide a framework for encoding time dependent dynamics as time independent systems. First, we create a time dependent simulation algorithm based on performing qubitization on the augmented clock system. Second, we define a natural generalization of multiproduct formulas for time-ordered exponentials.
  arXiv  Detail & Related papers  (2022-03-21T21:29:22Z)
• Proving Equivalence Between Complex Expressions Using Graph-to-Sequence Neural Models [0.0]
  We develop a graph-to-sequence neural network system for program equivalence. We extensively evaluate our system on a rich multi-type linear algebra expression language. Our machine learning system guarantees correctness for all true negatives, and ensures 0 false positive by design.
  arXiv  Detail & Related papers  (2021-06-01T20:45:42Z)
• FOREST: An Interactive Multi-tree Synthesizer for Regular Expressions [5.21480688623047]
  We present FOREST, a regular expression synthesizer for digital form validations. Forestry produces a regular expression that matches the desired pattern for the input values. We also present a new SMT encoding to synthesize capture conditions for a given regular expression.
  arXiv  Detail & Related papers  (2020-12-28T14:06:01Z)
• Contrastive Learning with Adversarial Perturbations for Conditional Text Generation [49.055659008469284]
  We propose a principled method to generate positive and negative samples for contrastive learning of seq2seq models. Specifically, we generate negative examples by adding small perturbations to the input sequence to minimize its conditional likelihood. We empirically show that our proposed method significantly improves the generalization of the seq2seq on three text generation tasks.
  arXiv  Detail & Related papers  (2020-12-14T06:20:27Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage linear programs. The proposed algorithm can be stopped in finite-time to return a solution endowed with a probabilistic guarantee on quality.
  arXiv  Detail & Related papers  (2020-12-07T14:58:16Z)
• Orbital MCMC [82.54438698903775]
  We propose two practical algorithms for constructing periodic orbits from any diffeomorphism. We also perform an empirical study demonstrating the practical advantages of both kernels.
  arXiv  Detail & Related papers  (2020-10-15T22:25:52Z)
• Pseudo-Convolutional Policy Gradient for Sequence-to-Sequence Lip-Reading [96.48553941812366]
  Lip-reading aims to infer the speech content from the lip movement sequence. Traditional learning process of seq2seq models suffers from two problems. We propose a novel pseudo-convolutional policy gradient (PCPG) based method to address these two problems.
  arXiv  Detail & Related papers  (2020-03-09T09:12:26Z)

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.