{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:32:28Z","timestamp":1744259548325,"version":"3.37.3"},"reference-count":0,"publisher":"IOS Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"abstract":"<jats:p>Interval temporal logics provide a natural framework for temporal reasoning about interval structures over linearly ordered domains, where intervals are taken as the primitive ontological entities. In this paper, we identify all fragments of Halpern and Shoham's interval temporal logic HS whose finite satisfiability problem is decidable. We classify them in terms of both relative expressive power and complexity. We show that there are exactly 62 expressively-different decidable fragments, whose complexity ranges from NP-complete to non-primitive recursive (all other HS fragments have been already shown to be undecidable).<\/jats:p>","DOI":"10.3233\/978-1-61499-098-7-199","type":"book-chapter","created":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:27:24Z","timestamp":1740133644000},"source":"Crossref","is-referenced-by-count":1,"title":["Interval Temporal Logics over Finite Linear Orders: the Complete Picture"],"prefix":"10.3233","author":[{"family":"Bresolin D.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Della Monica D.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Montanari A.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Sala P.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Sciavicco G.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2012"],"original-title":[],"deposited":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:06:15Z","timestamp":1740135975000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospressISSNISBN&issn=0922-6389&volume=242&spage=199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/978-1-61499-098-7-199","relation":{},"ISSN":["0922-6389"],"issn-type":[{"value":"0922-6389","type":"print"}],"subject":[],"published":{"date-parts":[[2012]]}}}