{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T06:40:27Z","timestamp":1721025627328},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"06","license":[{"start":{"date-parts":[[2019,2,28]],"date-time":"2019-02-28T00:00:00Z","timestamp":1551312000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Ramsey quantifiers are a natural object of study not only for logic and computer science but also for the formal semantics of natural language. Restricting attention to finite models leads to the natural question whether all Ramsey quantifiers are either polynomial-time computable or NP-hard, and whether we can give a natural characterization of the polynomial-time computable quantifiers. In this paper, we first show that there exist intermediate Ramsey quantifiers and then we prove a dichotomy result for a large and natural class of Ramsey quantifiers, based on a reasonable and widely believed complexity assumption. We show that the polynomial-time computable quantifiers in this class are exactly the constant-log-bounded Ramsey quantifiers.<\/jats:p>","DOI":"10.1017\/s0960129518000397","type":"journal-article","created":{"date-parts":[[2019,2,28]],"date-time":"2019-02-28T10:39:20Z","timestamp":1551350360000},"page":"896-908","source":"Crossref","is-referenced-by-count":0,"title":["Characterizing polynomial Ramsey quantifiers"],"prefix":"10.1017","volume":"29","author":[{"given":"Ronald","family":"de Haan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Szymanik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,2,28]]},"reference":[{"key":"S0960129518000397_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-013-9181-9"},{"key":"S0960129518000397_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.30"},{"key":"S0960129518000397_ref17","first-page":"338","volume-title":"Proceedings of the London Mathematical Society","author":"Ramsey","year":"1929"},{"key":"S0960129518000397_ref16","volume-title":"Quantifiers in Language and Logic","author":"Peters","year":"2006"},{"key":"S0960129518000397_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.016"},{"key":"S0960129518000397_ref9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008215718090"},{"key":"S0960129518000397_ref14","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"Lindstr\u00f6m","year":"1966","journal-title":"Theoria"},{"key":"S0960129518000397_ref8","volume-title":"Texts in Theoretical Computer Science. An EATCS Series","author":"Gr\u00e4del","year":"2007"},{"key":"S0960129518000397_ref13","first-page":"41","volume":"105","author":"Lokshtanov","year":"2011","journal-title":"Bulletin of the EATCS"},{"key":"S0960129518000397_ref7","volume-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"key":"S0960129518000397_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"S0960129518000397_ref6","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005330227480"},{"key":"S0960129518000397_ref11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"S0960129518000397_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"S0960129518000397_ref10","volume-title":"Descriptive Complexity. Texts in Computer Science","author":"Immerman","year":"1998"},{"key":"S0960129518000397_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.05.001"},{"key":"S0960129518000397_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00343-7"},{"key":"S0960129518000397_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90040-0"},{"key":"S0960129518000397_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"S0960129518000397_ref26","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008209019899"},{"key":"S0960129518000397_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.langsci.2017.01.006"},{"key":"S0960129518000397_ref24","volume-title":"Studies in Linguistics and Philosophy","author":"Szymanik","year":"2016"},{"key":"S0960129518000397_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s10988-010-9076-z"},{"key":"S0960129518000397_ref18","first-page":"216","volume-title":"Proceedings of the Tenth Annual ACM Symposium on Theory of Computing","author":"Schaefer","year":"1978"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129518000397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T06:22:01Z","timestamp":1721024521000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129518000397\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,28]]},"references-count":24,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["S0960129518000397"],"URL":"https:\/\/doi.org\/10.1017\/s0960129518000397","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,28]]}}}