{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:15Z","timestamp":1753894395852,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Linear Temporal Logic (LTL) is one of the most popular temporal logics, that\ncomes into play in a variety of branches of computer science. Among the various\nreasons of its widespread use there are its strong foundational properties: LTL\nis equivalent to counter-free omega-automata, to star-free omega-regular\nexpressions, and (by Kamp's theorem) to the First-Order Theory of Linear Orders\n(FO-TLO). Safety and co-safety languages, where a finite prefix suffices to\nestablish whether a word does not belong or belongs to the language,\nrespectively, play a crucial role in lowering the complexity of problems like\nmodel checking and reactive synthesis for LTL. SafetyLTL (resp., coSafetyLTL)\nis a fragment of LTL where only universal (resp., existential) temporal\nmodalities are allowed, that recognises safety (resp., co-safety) languages\nonly. The main contribution of this paper is the introduction of a fragment of\nFO-TLO, called SafetyFO, and of its dual coSafetyFO, which are expressively\ncomplete with respect to the LTL-definable safety and co-safety languages. We\nprove that they exactly characterize SafetyLTL and coSafetyLTL, respectively, a\nresult that joins Kamp's theorem, and provides a clearer view of the\ncharacterization of (fragments of) LTL in terms of first-order languages. In\naddition, it gives a direct, compact, and self-contained proof that any safety\nlanguage definable in LTL is definable in SafetyLTL as well. As a by-product,\nwe obtain some interesting results on the expressive power of the weak tomorrow\noperator of SafetyLTL, interpreted over finite and infinite words. Moreover, we\nprove that, when interpreted over finite words, SafetyLTL (resp. coSafetyLTL)\ndevoid of the tomorrow (resp., weak tomorrow) operator captures the safety\n(resp., co-safety) fragment of LTL over finite words.<\/jats:p>","DOI":"10.46298\/lmcs-19(3:13)2023","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T07:40:21Z","timestamp":1691653221000},"source":"Crossref","is-referenced-by-count":0,"title":["A first-order logic characterization of safety and co-safety languages"],"prefix":"10.46298","volume":"Volume 19, Issue 3","author":[{"given":"Alessandro","family":"Cimatti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Geatti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Gigante","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Montanari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Tonetta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2023,8,10]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/11716\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/11716\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T07:40:22Z","timestamp":1691653222000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(3:13)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2209.02307v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2209.02307v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2209.02307","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2209.02307","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"article-number":"10061"}}