{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T11:15:57Z","timestamp":1690974957624},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00493-018-4004-x","type":"journal-article","created":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T07:25:33Z","timestamp":1552461933000},"page":"923-932","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["VC-Dimensions of Short Presburger Formulas"],"prefix":"10.1007","volume":"39","author":[{"given":"Danny","family":"Nguyen","sequence":"first","affiliation":[]},{"given":"Igor","family":"Pak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"4004_CR1","doi-asserted-by":"publisher","first-page":"5889","DOI":"10.1090\/tran\/6659","volume":"368","author":"M. Aschenbrenner","year":"2016","unstructured":"M. Aschenbrenner, A. Dolich, D. Haskell, D. Macpherson and S. Starchenko: Vapnik-Chervonenkis density in some theories without the inde-pendence property, I, Trans. AMS\n                           368 (2016), 5889\u20135949.","journal-title":"Trans. AMS"},{"key":"4004_CR2","first-page":"957","volume":"16","author":"A. Barvinok","year":"2003","unstructured":"A. Barvinok and K. Woods: Short rational generating functions for lattice point problems, Jour. AMS\n                           16 (2003), 957\u2013979.","journal-title":"Jour. AMS"},{"key":"4004_CR3","unstructured":"A. Chernikov: Models theory and combinatorics, course notes, UCLA; available electronically at https:\/\/tinyurl.com\/y8ob6uyv."},{"key":"4004_CR4","first-page":"27","volume-title":"Proc. SIAM-AMS Symposium in Applied Mathematics","author":"M. J. Fischer","year":"1974","unstructured":"M. J. Fischer and M. O. Rabin: Super-Exponential Complexity of Presburger Arithmetic, in: Proc. SIAM-AMS Symposium in Applied Mathematics, AMS, Providence, RI, 1974, 27\u201341."},{"key":"4004_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1006\/jcss.1997.1477","volume":"54","author":"M. Karpinski","year":"1997","unstructured":"M. Karpinski and A. Macintyre: Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks, J. Comput. System Sci.\n                           54 (1997), 169\u2013176.","journal-title":"J. Comput. System Sci."},{"key":"4004_CR6","first-page":"149","volume-title":"Connections between model theory and algebraic and analytic geometry","author":"M. Karpinski","year":"2000","unstructured":"M. Karpinski and A. Macintyre: Approximating volumes and integrals in o-minimal and p-minimal theories, in: Connections between model theory and algebraic and analytic geometry, Seconda Univ. Napoli, Caserta, 2000, 149\u2013177."},{"key":"4004_CR7","doi-asserted-by":"publisher","first-page":"986","DOI":"10.1137\/17M1118907","volume":"32","author":"D. Nguyen","year":"2018","unstructured":"D. Nguyen and I. Pak: Enumeration of integer points in projections of unbounded polyhedra, SIAM J. Discrete Math.\n                           32 (2018), 986\u20131002.","journal-title":"SIAM J. Discrete Math."},{"key":"4004_CR8","first-page":"37","volume-title":"Proc. 58th FOCS, IEEE","author":"D. Nguyen","year":"2017","unstructured":"D. Nguyen and I. Pak: Short Presburger Arithmetic is hard, in: Proc. 58th FOCS, IEEE, Los Alamitos, CA, 2017, 37\u201348."},{"key":"4004_CR9","first-page":"173","volume":"8","author":"J. C. Lagarias","year":"1987","unstructured":"J. C. Lagarias and A. M. Odlyzko: Computing \u03c0(x): an analytic method, J. Al-gorithms\n                           8 (1987), 173\u2013191.","journal-title":"J. Al-gorithms"},{"key":"4004_CR10","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0022-0000(78)90021-1","volume":"16","author":"D. C. Oppen","year":"1978","unstructured":"D. C. Oppen: A 222pn upper bound on the complexity of Presburger arithmetic, J. Comput. System Sci.\n                           16 (1978), 323\u2013332.","journal-title":"J. Comput. System Sci."},{"key":"4004_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"N. Sauer: On the density of families of sets, J. Combin. Theory, Ser. A\n                           13 (1972), 145\u2013147.","journal-title":"J. Combin. Theory, Ser. A"},{"key":"4004_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S. Shelah","year":"1972","unstructured":"S. Shelah: A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math.\n                           41 (1972), 247\u2013261.","journal-title":"Pacific J. Math."},{"key":"4004_CR13","first-page":"1","volume-title":"Proc. Fifth STOC","author":"L. J. Stockmeyer","year":"1973","unstructured":"L. J. Stockmeyer and A. R. Meyer: Word problems requiring exponential time: preliminary report, in: Proc. Fifth STOC, ACM, New York, 1973, 1\u20139."},{"key":"4004_CR14","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1090\/S0025-5718-2011-02542-1","volume":"81","author":"T. Tao","year":"2012","unstructured":"T. Tao, E. Croot and H. Helfgott: Deterministic methods to find primes, Math. Comp.\n                           81 (2012), 1233\u20131246.","journal-title":"Math. Comp."},{"key":"4004_CR15","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik and A. Ja. \u010cervonenkis: The uniform convergence of frequencies of the appearance of events to their probabilitie, Theor. Probability Appl.\n                           16 (1971), 264\u2013280.","journal-title":"Theor. Probability Appl."},{"key":"4004_CR16","volume-title":"Statistical learning theory","author":"V. N. Vapnik","year":"1998","unstructured":"V. N. Vapnik: Statistical learning theory, John Wiley, New York, 1998."},{"key":"4004_CR17","first-page":"48","volume-title":"Proc. 1997 ISSAC","author":"V. D. Weispfenning","year":"1997","unstructured":"V. D. Weispfenning: Complexity and uniformity of elimination in Presburger arithmetic, in: Proc. 1997 ISSAC, ACM, New York, 1997, 48\u201353."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-018-4004-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-018-4004-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-018-4004-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T22:16:32Z","timestamp":1570227392000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-018-4004-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["4004"],"URL":"https:\/\/doi.org\/10.1007\/s00493-018-4004-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,13]]},"assertion":[{"value":"5 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}