{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T03:23:16Z","timestamp":1725679396254},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>With respect to the number of variables the border of decidability lies between 2 and 3: the two-variable fragment of first-order logic, FO2, has an exponential model property and hence NExpTime-complete satisfiability problem, while for the three-variable fragment, FO3, satisfiability is undecidable. In this paper we propose a rich subfragment of FO3, containing full FO2 (without equality), and show that it retains the finite model property and NExpTime complexity. Our fragment is obtained as an extension of the uniform one-dimensional variant of FO3.<\/jats:p>","DOI":"10.29007\/1xns","type":"proceedings-article","created":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T22:10:10Z","timestamp":1685830210000},"page":"205-185","source":"Crossref","is-referenced-by-count":1,"title":["An excursion to the border of decidability: between two- and three-variable logic"],"prefix":"10.29007","volume":"94","author":[{"given":"Oskar","family":"Fiuk","sequence":"first","affiliation":[]},{"given":"Emanuel","family":"Kieronski","sequence":"additional","affiliation":[]}],"member":"11545","event":{"name":"Proceedings of 24th International Conference on Logic for Programming, Artificial Intelligence and Reasoning"},"container-title":["EPiC Series in Computing"],"original-title":[],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T22:10:13Z","timestamp":1685830213000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/KVm2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/1xns","relation":{},"ISSN":["2398-7340"],"issn-type":[{"type":"print","value":"2398-7340"}],"subject":[]}}