{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T12:04:24Z","timestamp":1785240264818,"version":"3.55.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T00:00:00Z","timestamp":1784592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"UK EPSRC","award":["2760033 and EP\/X040518\/1"],"award-info":[{"award-number":["2760033 and EP\/X040518\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Reactive systems, which maintain ongoing interactions with their environment, are typically modeled using \u03c9-regular languages. These languages characterize system behavior with infinite-length execution traces and are represented as nondeterministic B\u00fcchi automata (NBAs) or \u03c9-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 \u03c9-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\u2019s 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\u00d7 and 1.5\u00d7 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.<\/jats:p>","DOI":"10.1145\/3803799","type":"journal-article","created":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T20:34:54Z","timestamp":1774730094000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Transition\u2011Based Acceptance for \u03c9\u2011Regular Expression Synthesis"],"prefix":"10.1145","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-9790-6362","authenticated-orcid":false,"given":"Charles","family":"Pert","sequence":"first","affiliation":[{"name":"Department of Computing, Imperial College London","place":["London, United Kingdom"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1365-8026","authenticated-orcid":false,"given":"Dalal","family":"Alrajeh","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London","place":["London, United Kingdom"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3318-8711","authenticated-orcid":false,"given":"Alessandra","family":"Russo","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London","place":["London, United Kingdom"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,21]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39176-7_6"},{"key":"e_1_3_4_3_2","volume-title":"Principles of Model Checking","author":"Baier Christel","year":"2008","unstructured":"Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. Retrieved from https:\/\/mitpress.mit.edu\/9780262026499\/principles-of-model-checking\/"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2007.364456"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2007.09.004"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99253-8_8"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1963.263416"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8928-6_23"},{"key":"e_1_3_4_9_2","article-title":"Transition-based vs Stated-based acceptance for automata over infinite words","volume":"147","author":"Casares Antonio","year":"2025","unstructured":"Antonio Casares. 2025. Transition-based vs Stated-based acceptance for automata over infinite words. Bulletin of the EATCS 147 (oct2025). Retrieved from https:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/864","journal-title":"Bulletin of the EATCS"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_6"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30500-2_31"},{"key":"e_1_3_4_13_2","volume-title":"Contributions to LTL and  \\(\\omega\\) -Automata for Model Checking","author":"Duret-Lutz Alexandre","year":"2017","unstructured":"Alexandre Duret-Lutz. 2017. Contributions to LTL and \\(\\omega\\) -Automata for Model Checking. Habilitation Thesis. Universit\u00e9 Pierre et Marie Curie (Paris 6). Retrieved from https:\/\/www.lrde.epita.fr\/adl\/dl\/adl.html"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13188-2_9"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80034-7"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-47705-8_15"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_1"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36135-9_20"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13089-2_24"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113500330"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.151.2"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02979-0_22"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2013-952"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.09.025"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/1196416"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","unstructured":"Swen Jacobs Guillermo A. P\u00e9rez Remco Abraham V\u00e9ronique Bruy\u00e8re Micha\u00ebl Cadilhac Maximilien Colange Charly Delfosse Tom van Dijk Alexandre Duret-Lutz Peter Faymonville et\u00a0al. 2024. The reactive synthesis competition (SYNTCOMP): 2018\u20132021. 26 5 (2024) 551\u2013567. DOI:10.1007\/s10009-024-00754-1","DOI":"10.1007\/s10009-024-00754-1"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90036-5"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58338-6_97"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/VISSOFT60811.2023.00018"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.070"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93442"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80013-X"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1609\/aiide.v11i1.12803"},{"key":"e_1_3_4_35_2","volume-title":"Infinite Words: Automata, Semigroups, Logic and Games","author":"Pin Jean-Eric","year":"2004","unstructured":"Jean-Eric Pin and Dominique Perrin. 2004. Infinite Words: Automata, Semigroups, Logic and Games. Retrieved from https:\/\/hal.science\/hal-00112831"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02253318"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73370-6_11"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44522-8_41"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-15579-1_22"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3803799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T11:41:27Z","timestamp":1785238887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3803799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,21]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1145\/3803799"],"URL":"https:\/\/doi.org\/10.1145\/3803799","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,21]]},"assertion":[{"value":"2025-08-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-07-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}