{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:20Z","timestamp":1753894400960,"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>A classic result by Stockmeyer gives a non-elementary lower bound to the\nemptiness problem for star-free generalized regular expressions. This result is\nintimately connected to the satisfiability problem for interval temporal logic,\nnotably for formulas that make use of the so-called chop operator. Such an\noperator can indeed be interpreted as the inverse of the concatenation\noperation on regular languages, and this correspondence enables reductions\nbetween non-emptiness of star-free generalized regular expressions and\nsatisfiability of formulas of the interval temporal logic of chop under the\nhomogeneity assumption. In this paper, we study the complexity of the\nsatisfiability problem for suitable weakenings of the chop interval temporal\nlogic, that can be equivalently viewed as fragments of Halpern and Shoham\ninterval logic. We first consider the logic $\\mathsf{BD}_{hom}$ featuring\nmodalities $B$, for \\emph{begins}, corresponding to the prefix relation on\npairs of intervals, and $D$, for \\emph{during}, corresponding to the infix\nrelation. The homogeneous models of $\\mathsf{BD}_{hom}$ naturally correspond to\nlanguages defined by restricted forms of regular expressions, that use union,\ncomplementation, and the inverses of the prefix and infix relations. Such a\nfragment has been recently shown to be PSPACE-complete . In this paper, we\nstudy the extension $\\mathsf{BD}_{hom}$ with the temporal neighborhood modality\n$A$ (corresponding to the Allen relation \\emph{Meets}), and prove that it\nincreases both its expressiveness and complexity. In particular, we show that\nthe resulting logic $\\mathsf{BDA}_{hom}$ is EXPSPACE-complete.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:23)2024","type":"journal-article","created":{"date-parts":[[2024,3,24]],"date-time":"2024-03-24T16:50:07Z","timestamp":1711299007000},"source":"Crossref","is-referenced-by-count":0,"title":["The addition of temporal neighborhood makes the logic of prefixes and sub-intervals EXPSPACE-complete"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"L.","family":"Bozzelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Montanari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Peron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Sala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2024,3,22]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/13274\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/13274\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,24]],"date-time":"2024-03-24T16:50:07Z","timestamp":1711299007000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,22]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:23)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2202.07881v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2202.07881v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2202.07881v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2202.07881","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2202.07881","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,3,22]]},"article-number":"9092"}}