{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,10]],"date-time":"2023-09-10T10:11:34Z","timestamp":1694340694312},"reference-count":15,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T00:00:00Z","timestamp":1567382400000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100007185","name":"University of California, Los Angeles","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006747","name":"San Francisco State University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006747","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider an expansion of Presburger arithmetic which allows multiplication by <jats:italic>k<\/jats:italic> parameters . A formula in this language defines a parametric set  as  varies in , and we examine the counting function  as a function of <jats:bold>t<\/jats:bold>. For a single parameter, it is known that  can be expressed as an eventual quasi\u2010polynomial (there is a period <jats:italic>m<\/jats:italic> such that, for sufficiently large <jats:italic>t<\/jats:italic>, the function is polynomial on each of the residue classes mod <jats:italic>m<\/jats:italic>). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming ) we construct a parametric set  such that  is not even polynomial\u2010time computable on input . In contrast, for parametric sets  with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that  is always polynomial\u2010time computable in the size of <jats:bold>t<\/jats:bold>, and in fact can be represented using the gcd and similar\u00a0functions.<\/jats:p>","DOI":"10.1002\/malq.201800068","type":"journal-article","created":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T06:07:10Z","timestamp":1567490830000},"page":"237-250","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parametric Presburger arithmetic: complexity of counting and quantifier elimination"],"prefix":"10.1002","volume":"65","author":[{"given":"Tristram","family":"Bogart","sequence":"first","affiliation":[{"name":"Departamento de Matem\u00e1ticas Universidad de Los Andes Carrera 1 No. 18a 10 111711 Bogot\u00e1 Colombia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Goodrick","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1ticas Universidad de Los Andes Carrera 1 No. 18a 10 111711 Bogot\u00e1 Colombia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Department of Mathematics University of Michigan Ann Arbor, 530 Church Street Ann Arbor MI 48109\u20101043 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Woods","sequence":"additional","affiliation":[{"name":"Department of Mathematics Oberlin College 10 N. Professor St. Oberlin OH 44074 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2019,9,2]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.4.769"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-03-00428-4"},{"issue":"4","key":"e_1_2_8_4_1","article-title":"Parametric Presburger arithmetic: logic, combinatorics, and quasi\u2010polynomial behavior","volume":"2017","author":"Bogart T.","year":"2017","journal-title":"Discrete Anal."},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1973.11993265"},{"key":"e_1_2_8_7_1","first-page":"27","volume-title":"Complexity of Computation, Proceedings of a Symposium Held in New York City","author":"Fischer M. J.","year":"1974"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.201600012"},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90136-3"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39368-6"},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.13"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90021-1"},{"key":"e_1_2_8_13_1","volume-title":"Theory of Linear and Integer Programming, Wiley\u2010Interscience Series in Discrete Math","author":"Schrijver A.","year":"1986"},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90025-U"},{"issue":"1","key":"e_1_2_8_15_1","first-page":"44","article-title":"The unreasonable ubiquitousness of quasi\u2010polynomials","volume":"21","author":"Woods K.","year":"2014","journal-title":"Electron. J. Comb."},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2015.4"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201800068","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201800068","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/malq.201800068","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201800068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T17:53:12Z","timestamp":1694281992000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201800068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1002\/malq.201800068"],"URL":"https:\/\/doi.org\/10.1002\/malq.201800068","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]},"assertion":[{"value":"2018-10-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-16","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}