{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:44Z","timestamp":1750307204637,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/G020604\/1"],"award-info":[{"award-number":["EP\/G020604\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure\n            <jats:italic>B<\/jats:italic>\n            . This may be seen as a natural generalisation of the nonuniform quantified constraint satisfaction problem QCSP(\n            <jats:italic>B<\/jats:italic>\n            ). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterizes definability in positive equality-free FO. Through an algebraic method, we derive a complete complexity classification for our problems as\n            <jats:italic>B<\/jats:italic>\n            ranges over structures of size at most three. Specifically, each problem either is in L, is NP-complete, is co-NP-complete, or is Pspace-complete.\n          <\/jats:p>","DOI":"10.1145\/2071368.2071373","type":"journal-article","created":{"date-parts":[[2012,1,31]],"date-time":"2012-01-31T14:49:20Z","timestamp":1328021360000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Positive First-Order Logic without Equality"],"prefix":"10.1145","volume":"13","author":[{"given":"Florent","family":"Madelaine","sequence":"first","affiliation":[{"name":"Clermont Univ\u00e9rsit, Univ\u00e9rsit d\u2019Auvergne"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[{"name":"Durham University"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"volume-title":"Proceedings of the 60th Workshop on General Algebra.","year":"2000","author":"B\u00f6rner F.","key":"e_1_2_1_1_1"},{"volume-title":"Complexity of Constraints: An Overview of Current Research Themes","series-title":"Lecture Notes in Computer Science","author":"B\u00f6rner F.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"B\u00f6rner F. Krokhin A. Bulatov A. and Jeavons P. 2002. Quantified constraints and surjective polymorphisms. Tech. rep. PRG-RR-02-11 Oxford University. B\u00f6rner F. Krokhin A. Bulatov A. and Jeavons P. 2002. Quantified constraints and surjective polymorphisms. Tech. rep. PRG-RR-02-11 Oxford University."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668572"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Creignou N. Khanna S. and Sudan M. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs. Creignou N. Khanna S. and Sudan M. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs.","DOI":"10.1137\/1.9780898718546"},{"volume-title":"A Mathematical Introduction to Logic","author":"Enderton H. B.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322037"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.15"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.27"},{"key":"e_1_2_1_16_1","unstructured":"Martin B. 2006. Dichotomies and duality in first-order model checking problems. CoRR abs\/cs\/0609022. Martin B. 2006. Dichotomies and duality in first-order model checking problems. CoRR abs\/cs\/0609022."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69407-6_45"},{"key":"e_1_2_1_18_1","unstructured":"Martin B. 2008b. Model checking positive equality-free FO: Boolean structures and digraphs of size three. CoRR abs\/0808.0647. Martin B. 2008b. Model checking positive equality-free FO: Boolean structures and digraphs of size three. CoRR abs\/0808.0647."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886008.1886042"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780342_36"},{"volume-title":"Proceedings of the 24th International Workshop on Computer Science Logic. 426--438","author":"Martin B.","key":"e_1_2_1_21_1"},{"volume-title":"Computational Complexity","author":"Papadimitriou C.","key":"e_1_2_1_22_1"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071368.2071373","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071368.2071373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071368.2071373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071368.2071373"],"URL":"https:\/\/doi.org\/10.1145\/2071368.2071373","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}