{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:44:23Z","timestamp":1767339863303,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T00:00:00Z","timestamp":1450051200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"name":"Austrian Science Fund","award":["P 26696"],"award-info":[{"award-number":["P 26696"]}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["259385"],"award-info":[{"award-number":["259385"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study the computational complexity of the FO model checking problem on\ninterval graphs, i.e., intersection graphs of intervals on the real line. The\nmain positive result is that FO model checking and successor-invariant FO model\nchecking can be solved in time O(n log n) for n-vertex interval graphs with\nrepresentations containing only intervals with lengths from a prescribed finite\nset. We complement this result by showing that the same is not true if the\nlengths are restricted to any set that is dense in an open subset, e.g., in the\nset $(1, 1 + \\varepsilon)$.<\/jats:p>","DOI":"10.2168\/lmcs-11(4:11)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:46:40Z","timestamp":1479736000000},"source":"Crossref","is-referenced-by-count":5,"title":["FO Model Checking of Interval Graphs"],"prefix":"10.46298","volume":"Volume 11, Issue 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":false,"given":"Robert","family":"Ganian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2125-1514","authenticated-orcid":false,"given":"Petr","family":"Hlineny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8680-0890","authenticated-orcid":false,"given":"Daniel","family":"Kral","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Obdrzalek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jarett","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Teska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2015,12,14]]},"reference":[{"key":"1145:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1612\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1612\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:07:52Z","timestamp":1681243672000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1612"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,14]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(4:11)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1302.6043","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1302.6043","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,12,14]]},"article-number":"1612"}}