{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:42:32Z","timestamp":1769751752967,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["852769"],"award-info":[{"award-number":["852769"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533372","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Geometric decision procedures and the VC dimension of linear arithmetic theories"],"prefix":"10.1145","author":[{"given":"Dmitry","family":"Chistikov","sequence":"first","affiliation":[{"name":"Centre for Discrete Mathematics and its Applications, Department of Computer Science, University of Warwick, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Haase","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessio","family":"Mansutti","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6659"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.252.8"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90037-7"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071596.1071601"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"e_1_3_2_1_6_1","first-page":"1","article-title":"The Taming of the Semi-Linear Set. In Proc. International Colloquium on Automata, Languages, and Programming, ICALP(LIPIcs, Vol.\u00a055)","volume":"128","author":"Chistikov Dmitry","year":"2016","unstructured":"Dmitry Chistikov and Christoph Haase . 2016 . The Taming of the Semi-Linear Set. In Proc. International Colloquium on Automata, Languages, and Programming, ICALP(LIPIcs, Vol.\u00a055) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 128 : 1 \u2013 128 :13. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.128 10.4230\/LIPIcs.ICALP.2016.128 Dmitry Chistikov and Christoph Haase. 2016. The Taming of the Semi-Linear Set. In Proc. International Colloquium on Automata, Languages, and Programming, ICALP(LIPIcs, Vol.\u00a055). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 128:1\u2013128:13. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.128","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99253-8_12"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54345-7_57"},{"key":"e_1_3_2_1_9_1","volume-title":"Proc. International Symposium on Theoretical Aspects of Computer Science, STACS(LIPIcs, Vol.\u00a014)","author":"Durand-Gasselin Antoine","year":"2012","unstructured":"Antoine Durand-Gasselin and Peter Habermehl . 2012 . Ehrenfeucht-Fra\u00efss\u00e9 goes elementarily automatic for structures of bounded degree . In Proc. International Symposium on Theoretical Aspects of Computer Science, STACS(LIPIcs, Vol.\u00a014) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 242\u2013253. https:\/\/doi.org\/10.4230\/LIPIcs.STACS. 2012.242 10.4230\/LIPIcs.STACS.2012.242 Antoine Durand-Gasselin and Peter Habermehl. 2012. Ehrenfeucht-Fra\u00efss\u00e9 goes elementarily automatic for structures of bounded degree. In Proc. International Symposium on Theoretical Aspects of Computer Science, STACS(LIPIcs, Vol.\u00a014). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 242\u2013253. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.242"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(69)90070-2"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204006"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61576-8_77"},{"key":"#cr-split#-e_1_3_2_1_14_1.1","doi-asserted-by":"crossref","unstructured":"Seymour Ginsburg and Edwin\u00a0H. Spanier. 1964. Bounded ALGOL-like languages. Trans. Amer. Math. Soc.(1964) 333-368. https:\/\/doi.org\/10.2307\/1994067 10.2307\/1994067","DOI":"10.1090\/S0002-9947-1964-0181500-1"},{"key":"#cr-split#-e_1_3_2_1_14_1.2","doi-asserted-by":"crossref","unstructured":"Seymour Ginsburg and Edwin\u00a0H. Spanier. 1964. Bounded ALGOL-like languages. Trans. Amer. Math. Soc.(1964) 333-368. https:\/\/doi.org\/10.2307\/1994067","DOI":"10.1090\/S0002-9947-1964-0181500-1"},{"key":"e_1_3_2_1_15_1","first-page":"285","article-title":"Semigroups, Presburger formulas, and languages.Pacific J","volume":"16","author":"Ginsburg Seymour","year":"1966","unstructured":"Seymour Ginsburg and Edwin\u00a0 H. Spanier . 1966 . Semigroups, Presburger formulas, and languages.Pacific J . Math. 16 , 2 (1966), 285 \u2013 296 . http:\/\/projecteuclid.org\/euclid.pjm\/1102994974 Seymour Ginsburg and Edwin\u00a0H. Spanier. 1966. Semigroups, Presburger formulas, and languages.Pacific J. Math. 16, 2 (1966), 285\u2013296. http:\/\/projecteuclid.org\/euclid.pjm\/1102994974","journal-title":"Math."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0742419-0"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785850"},{"key":"e_1_3_2_1_18_1","first-page":"1","article-title":"The Optimal Sample Complexity of PAC Learning","volume":"17","author":"Hanneke Steve","year":"2016","unstructured":"Steve Hanneke . 2016 . The Optimal Sample Complexity of PAC Learning . J. Mach. Learn. Res. 17 , 38 (2016), 1 \u2013 15 . http:\/\/jmlr.org\/papers\/v17\/15-389.html Steve Hanneke. 2016. The Optimal Sample Complexity of PAC Learning. J. Mach. Learn. Res. 17, 38 (2016), 1\u201315. http:\/\/jmlr.org\/papers\/v17\/15-389.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_19_1","volume-title":"Wright","author":"Hardy Godfrey H.","year":"2008","unstructured":"Godfrey H. Hardy and Edward M . Wright . 2008 . An Introduction to the Theory of Numbers. Oxford University Press . Godfrey H. Hardy and Edward M. Wright. 2008. An Introduction to the Theory of Numbers. Oxford University Press."},{"key":"e_1_3_2_1_20_1","first-page":"147","article-title":"A Simple Proof for the Math 624 Upper Bound of the Inequivalence Problem for Semilinear Sets","volume":"22","author":"Huynh T.","year":"1986","unstructured":"Dung\u00a0 T. Huynh . 1986 . A Simple Proof for the Math 624 Upper Bound of the Inequivalence Problem for Semilinear Sets . Elektron. Inf.verarb. Kybern. 22 , 4 (1986), 147 \u2013 156 . Dung\u00a0T. Huynh. 1986. A Simple Proof for the Math 624 Upper Bound of the Inequivalence Problem for Semilinear Sets. Elektron. Inf.verarb. Kybern. 22, 4 (1986), 147\u2013156.","journal-title":"Elektron. Inf.verarb. Kybern."},{"key":"e_1_3_2_1_21_1","first-page":"291","article-title":"The Complexity of Semilinear Sets","volume":"18","author":"Huynh Thiet-Dung","year":"1982","unstructured":"Thiet-Dung Huynh . 1982 . The Complexity of Semilinear Sets . Elektron. Inf.verarb. Kybern. 18 , 6 (1982), 291 \u2013 338 . Thiet-Dung Huynh. 1982. The Complexity of Semilinear Sets. Elektron. Inf.verarb. Kybern. 18, 6 (1982), 291\u2013338.","journal-title":"Elektron. Inf.verarb. Kybern."},{"key":"e_1_3_2_1_22_1","unstructured":"Marek Karpinski and Angus Macintyre. 1997. Approximating volumes and integrals in o-minimal and p-minimal theories. Connections between model theory and algebraic and analytic geometry 6(1997) 149\u2013177.  Marek Karpinski and Angus Macintyre. 1997. Approximating volumes and integrals in o-minimal and p-minimal theories. Connections between model theory and algebraic and analytic geometry 6(1997) 149\u2013177."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1477"},{"key":"e_1_3_2_1_24_1","volume-title":"An introduction to computational learning theory","author":"Kearns J","unstructured":"Michael\u00a0 J Kearns and Umesh Vazirani . 1994. An introduction to computational learning theory . MIT Press . Michael\u00a0J Kearns and Umesh Vazirani. 1994. An introduction to computational learning theory. MIT Press."},{"key":"e_1_3_2_1_25_1","volume-title":"Complexity of Problems of Commutative Grammars. Log. Methods Comput. Sci. 11, 1","author":"Kopczy\u0144ski Eryk","year":"2015","unstructured":"Eryk Kopczy\u0144ski . 2015. Complexity of Problems of Commutative Grammars. Log. Methods Comput. Sci. 11, 1 ( 2015 ). https:\/\/doi.org\/10.2168\/LMCS-11(1:9)2015 10.2168\/LMCS-11(1:9)2015 Eryk Kopczy\u0144ski. 2015. Complexity of Problems of Commutative Grammars. Log. Methods Comput. Sci. 11, 1 (2015). https:\/\/doi.org\/10.2168\/LMCS-11(1:9)2015"},{"key":"e_1_3_2_1_26_1","volume-title":"Theory of Computation","author":"Kozen Dexter","unstructured":"Dexter Kozen . 2006. Theory of Computation . Springer . Dexter Kozen. 2006. Theory of Computation. Springer."},{"key":"e_1_3_2_1_27_1","series-title":"SIAM and MOS. https:\/\/doi.org\/10.1137\/1.9781611972443","volume-title":"Vol.\u00a0MO14","author":"De Loera Jes\u00fas","unstructured":"Jes\u00fas A.\u00a0 De Loera , Raymond Hemmecke , and Matthias K\u00f6ppe . 2013. Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM series on optimization , Vol.\u00a0MO14 . SIAM and MOS. https:\/\/doi.org\/10.1137\/1.9781611972443 10.1137\/1.9781611972443 Jes\u00fas A.\u00a0De Loera, Raymond Hemmecke, and Matthias K\u00f6ppe. 2013. Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM series on optimization, Vol.\u00a0MO14. SIAM and MOS. https:\/\/doi.org\/10.1137\/1.9781611972443"},{"key":"e_1_3_2_1_28_1","volume-title":"Vol.\u00a0212","author":"Matou\u0161ek Ji\u0159\u00ed","unstructured":"Ji\u0159\u00ed Matou\u0161ek . 2002. Lectures on discrete geometry. Graduate texts in mathematics , Vol.\u00a0212 . Springer . Ji\u0159\u00ed Matou\u0161ek. 2002. Lectures on discrete geometry. Graduate texts in mathematics, Vol.\u00a0212. Springer."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1118907"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-018-4004-x"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1151146"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90021-1"},{"key":"e_1_3_2_1_33_1","volume-title":"Polyhedral Geometry and Linear Optimization (Summer Semester","author":"Paffenholz Andreas","year":"2010","unstructured":"Andreas Paffenholz . 2013. Polyhedral Geometry and Linear Optimization (Summer Semester 2010 ). Available at http:\/\/www.mathematik.tu-darmstadt.de\/~paffenholz\/daten\/preprints\/ln.pdf. Andreas Paffenholz. 2013. Polyhedral Geometry and Linear Optimization (Summer Semester 2010). Available at http:\/\/www.mathematik.tu-darmstadt.de\/~paffenholz\/daten\/preprints\/ln.pdf."},{"key":"e_1_3_2_1_34_1","volume-title":"Proc.","author":"Piskac Ruzica","unstructured":"Ruzica Piskac and Viktor Kuncak . 2008. Linear Arithmetic with Stars . In Proc. Computer Aided Verification, CAV(Lecture Notes in Computer Science, Vol.\u00a05123). Springer , 268\u2013280. https:\/\/doi.org\/10.1007\/978-3-540-70545-1_25 10.1007\/978-3-540-70545-1_25 Ruzica Piskac and Viktor Kuncak. 2008. Linear Arithmetic with Stars. In Proc. Computer Aided Verification, CAV(Lecture Notes in Computer Science, Vol.\u00a05123). Springer, 268\u2013280. https:\/\/doi.org\/10.1007\/978-3-540-70545-1_25"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273753"},{"key":"e_1_3_2_1_36_1","unstructured":"Moj\u017cesz Presburger. 1929. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du I congres de Mathematiciens des Pays Slaves. 92\u2013101.  Moj\u017cesz Presburger. 1929. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du I congres de Mathematiciens des Pays Slaves. 92\u2013101."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80004-5"},{"key":"e_1_3_2_1_38_1","volume-title":"Convex Analysis","author":"Rockafellar Tyrrell","unstructured":"R.\u00a0 Tyrrell Rockafellar . 1970. Convex Analysis . Princeton University Press . R.\u00a0Tyrrell Rockafellar. 1970. Convex Analysis. Princeton University Press."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"e_1_3_2_1_40_1","volume-title":"Theory of linear and integer programming","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 1999. Theory of linear and integer programming . Wiley . Alexander Schrijver. 1999. Theory of linear and integer programming. Wiley."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071596.1071602"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90015-5"},{"key":"e_1_3_2_1_43_1","first-page":"247","article-title":"A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific J","volume":"41","author":"Shelah Saharon","year":"1972","unstructured":"Saharon Shelah . 1972 . A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific J . Math. 41 , 1 (1972), 247 \u2013 261 . http:\/\/projecteuclid.org\/euclid.pjm\/1102968432 Saharon Shelah. 1972. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific J. Math. 41, 1 (1972), 247\u2013261. http:\/\/projecteuclid.org\/euclid.pjm\/1102968432","journal-title":"Math."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90076-6"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258746"},{"key":"e_1_3_2_1_46_1","volume-title":"Proc. International Symposium on Symbolic and Algebraic Computation, ISSAC. ACM, 129\u2013136","author":"Weispfenning Volker","year":"1999","unstructured":"Volker Weispfenning . 1999 . Mixed Real-Integer Linear Quantifier Elimination . In Proc. International Symposium on Symbolic and Algebraic Computation, ISSAC. ACM, 129\u2013136 . https:\/\/doi.org\/10.1145\/309831.309888 10.1145\/309831.309888 Volker Weispfenning. 1999. Mixed Real-Integer Linear Quantifier Elimination. In Proc. International Symposium on Symbolic and Algebraic Computation, ISSAC. ACM, 129\u2013136. https:\/\/doi.org\/10.1145\/309831.309888"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46419-0_1"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Haifa Israel","acronym":"LICS '22","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"]},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":48,"alternative-id":["10.1145\/3531130.3533372","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533372","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}