{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:36Z","timestamp":1750308576307,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T00:00:00Z","timestamp":1502928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Basque Government Project S-PE12UN050","award":["SAI12\/219"],"award-info":[{"award-number":["SAI12\/219"]}]},{"DOI":"10.13039\/501100003451","name":"University of the Basque Country","doi-asserted-by":"crossref","award":["UFI11\/45"],"award-info":[{"award-number":["UFI11\/45"]}],"id":[{"id":"10.13039\/501100003451","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Spanish Project FORMALISM","award":["TIN2007-66523"],"award-info":[{"award-number":["TIN2007-66523"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>The focus of this work is first-order model checking, by which we refer to the problem of deciding whether or not a given first-order sentence is satisfied by a given finite structure. In particular, we aim to understand on which sets of sentences this problem is tractable, in the sense of parameterized complexity theory. To this end, we define the notion of a graph-like sentence set; the definition is inspired by previous work on first-order model checking wherein the permitted connectives and quantifiers were restricted. Our main theorem is the complete tractability classification of such graph-like sentence sets, which is (to our knowledge) the first complexity classification theorem concerning a class of sentences that has no restriction on the connectives and quantifiers. To present and prove our classification, we introduce and develop a novel complexity-theoretic framework that is built on parameterized complexity and includes new notions of reduction.<\/jats:p>","DOI":"10.1145\/3073409","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Tractability Frontier of Graph-Like First-Order Query Sets"],"prefix":"10.1145","volume":"64","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[{"name":"Universidad del Pa\u00eds Vasco and IKERBASQUE, Basque Foundation for Science, Spain"}]}],"member":"320","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Isolde Adler and Mark Weyer. 2012. Tree-width for first order formulae. Logical Methods in Computer Science 8 1 Article No. 32.  Isolde Adler and Mark Weyer. 2012. Tree-width for first order formulae. Logical Methods in Computer Science 8 1 Article No. 32.","key":"e_1_2_1_1_1","DOI":"10.2168\/LMCS-8(1:32)2012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT\u201914)","author":"Bova Simone","year":"2014","unstructured":"Simone Bova and Hubie Chen . 2014 . The complexity of width minimization for existential positive queries . In Proceedings of the 17th International Conference on Database Theory (ICDT\u201914) . 235--244. Simone Bova and Hubie Chen. 2014. The complexity of width minimization for existential positive queries. In Proceedings of the 17th International Conference on Database Theory (ICDT\u201914). 235--244."},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/2559946"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/LICS.2012.31"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/j.jcss.2010.04.003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/978-3-642-39212-2_14"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th International Conference on Database Theory (ICDT\u201915)","author":"Chen Hubie","year":"2015","unstructured":"Hubie Chen and Stefan Mengel . 2015 . A trichotomy in the complexity of counting answers to conjunctive queries . In Proceedings of the 18th International Conference on Database Theory (ICDT\u201915) . 110--126. Hubie Chen and Stefan Mengel. 2015. A trichotomy in the complexity of counting answers to conjunctive queries. In Proceedings of the 18th International Conference on Database Theory (ICDT\u201915). 110--126."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/2902251.2902279"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/2463664.2463669"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/2603088.2603107"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/2751316"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1007\/978-3-540-70575-8_48"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/FOCS.2014.22"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/2448496.2448508"},{"unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1206035.1206036"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/380752.380867"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1007\/978-3-642-40627-0_32"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1006\/jcss.2000.1713"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_22_1","series-title":"Algorithms and Theory of Computation Handbook (2 ed.)","volume-title":"Special Topics and Techniques","author":"Schweikardt Nicole","unstructured":"Nicole Schweikardt , Thomas Schwentick , and Luc Segoufin . 2009. Database theory: Query languages . In Algorithms and Theory of Computation Handbook (2 ed.) , M. J. Atallah and M. Blanton (Eds.). Vol. 2 : Special Topics and Techniques . CRC Press , Boca Raton, FL , 19. Nicole Schweikardt, Thomas Schwentick, and Luc Segoufin. 2009. Database theory: Query languages. In Algorithms and Theory of Computation Handbook (2 ed.), M. J. Atallah and M. Blanton (Eds.). Vol. 2: Special Topics and Techniques. CRC Press, Boca Raton, FL, 19."},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/212433.212474"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3073409","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3073409","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:50Z","timestamp":1750273490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3073409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,17]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3073409"],"URL":"https:\/\/doi.org\/10.1145\/3073409","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,8,17]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}