EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Transition‑Based Acceptance for ω‑Regular Expression Synthesis

Charles Pert, Dalal Alrajeh, Alessandra Russo

Formal Aspects of Computing · 30.09.2026 · 38 (3) · 1-23

DOI: 10.1145/3803799 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Formal Aspects of Computing, online erschienen am 21.07.2026. Verfasst von Charles Pert und 2 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: UK EPSRC.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Reactive systems, which maintain ongoing interactions with their environment, are typically modeled using ω-regular languages. These languages characterize system behavior with infinite-length execution traces and are represented as nondeterministic Büchi automata (NBAs) or ω-regular expressions. Existing methods for synthesizing expressions from NBAs only handle state-based acceptance. This limitation forces the conversion of compact transition-based NBAs into larger state-based NBAs before synthesis. This article introduces the first direct synthesis method for ω-regular expressions from transition-based NBAs, eliminating the need for this transformation. The method works by decomposing an NBA into triplets of nondeterministic finite automata, subsuming existing pair-based decompositions to handle transition-based acceptance. We prove that our decomposition is correct, establishing our method’s soundness and completeness. We discuss the time and descriptional complexity of our method. Our empirical evaluation on 185 linear temporal logic formulas supports our hypothesis; transition-based synthesis reduces postfix size by 4.1× and 1.5× for recurrence and reactivity properties, respectively. We also analyze the structural NBA factors that determine when the transition-based NBA will yield a more compact expression and develop this into a simple criterion that, when applied, yields expressions that are at least as compact as those obtained by direct state-based synthesis.

Förderung

  • UK EPSRC

Zitieren

APA

Pert, C., Alrajeh, D., & Russo, A. (2026). Transition‑Based Acceptance for ω‑Regular Expression Synthesis. Formal Aspects of Computing, 38(3), 1-23. https://doi.org/10.1145/3803799

Vancouver

Pert C, Alrajeh D, Russo A. Transition‑Based Acceptance for ω‑Regular Expression Synthesis. Formal Aspects of Computing. 2026;38(3):1-23. doi:10.1145/3803799

BibTeX
@article{Pert2026,
  author = {Pert, Charles and Alrajeh, Dalal and Russo, Alessandra},
  title = {Transition‑Based Acceptance for ω‑Regular Expression Synthesis},
  journal = {Formal Aspects of Computing},
  year = {2026},
  volume = {38},
  number = {3},
  pages = {1--23},
  doi = {10.1145/3803799}
}
Kostenlos starten →