{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T23:00:18Z","timestamp":1790636418033,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,7,14]],"date-time":"2014-07-14T00:00:00Z","timestamp":1405296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-001"],"award-info":[{"award-number":["ANR-11-BS02-001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,7,14]]},"DOI":"10.1145\/2603088.2603092","type":"proceedings-article","created":{"date-parts":[[2014,7,28]],"date-time":"2014-07-28T13:21:45Z","timestamp":1406553705000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Subclasses of presburger arithmetic and the weak EXP hierarchy"],"prefix":"10.1145","author":[{"given":"Christoph","family":"Haase","sequence":"first","affiliation":[{"name":"Laboratoire Sp\u00e9cification et V\u00e9rification (LSV), CNRS, \u00c9cole Normale Sup\u00e9rieure (ENS) de Cachan, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,7,14]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"781","article-title":"PRIMES is","volume":"2","author":"Agrawal Manindra","year":"2002","unstructured":"Manindra Agrawal , Neeraj Kayal , and Nitin Saxena . PRIMES is in P. Annals of Mathematics , 2 : 781 -- 793 , 2002 . Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 2:781--793, 2002.","journal-title":"P. Annals of Mathematics"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"Arora Sanjeev","year":"2009","unstructured":"Sanjeev Arora and Boaz Barak . Computational Complexity: A Modern Approach . Cambridge University Press , New York, NY, USA , 1 st edition, 2009 . Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009.","edition":"1"},{"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","first-page":"1","volume-title":"A tribute to Maurice Boffa","author":"B\u00e8s Alexis","year":"2002","unstructured":"Alexis B\u00e8s . A survey of arithmetical definability . In A tribute to Maurice Boffa , pages 1 -- 54 . Soci\u00e9t\u00e9 Math\u00e9matique de Belgique , 2002 . Alexis B\u00e8s. A survey of arithmetical definability. In A tribute to Maurice Boffa, pages 1--54. Soci\u00e9t\u00e9 Math\u00e9matique de Belgique, 2002."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1976-0396605-3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1216\/RMJ-2010-40-1-117"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"e_1_3_2_1_8_1","first-page":"91","article-title":"Theorem proving in arithmetic without multiplication","volume":"7","author":"Cooper D. C.","year":"1972","unstructured":"D. C. Cooper . Theorem proving in arithmetic without multiplication . Machine Intelligence , 7 : 91 -- 99 , 1972 . D. C. Cooper. Theorem proving in arithmetic without multiplication. Machine Intelligence, 7:91--99, 1972.","journal-title":"Machine Intelligence"},{"key":"e_1_3_2_1_9_1","first-page":"242","volume-title":"29th International Symposium on Theoretical Aspects of Computer Science, volume 14 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Durand-Gasselin Antoine","year":"2012","unstructured":"Antoine Durand-Gasselin and Peter Habermehl . Ehrenfeucht-Fr\u00e4iss\u00e9 goes elementarily automatic for structures of bounded degree. In Christoph Durr and Thomas Wilke, editors , 29th International Symposium on Theoretical Aspects of Computer Science, volume 14 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 242 -- 253 , Dagstuhl, Germany , 2012 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik. Antoine Durand-Gasselin and Peter Habermehl. Ehrenfeucht-Fr\u00e4iss\u00e9 goes elementarily automatic for structures of bounded degree. In Christoph Durr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pages 242--253, Dagstuhl, Germany, 2012. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204006"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/978-3-7091-9459-1_5","volume-title":"Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation","author":"Fischer Michael J.","year":"1998","unstructured":"Michael J. Fischer and Michael O. Rabin . Super-exponential complexity of Presburger arithmetic . In Bob F. Caviness and Jeremy R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation , pages 122 -- 135 . Springer Vienna , 1998 . Michael J. Fischer and Michael O. Rabin. Super-exponential complexity of Presburger arithmetic. In Bob F. Caviness and Jeremy R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 122--135. Springer Vienna, 1998."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90115-3"},{"key":"e_1_3_2_1_14_1","volume-title":"The mathematical theory of context free languages","author":"Ginsburg Seymour","year":"1966","unstructured":"Seymour Ginsburg . The mathematical theory of context free languages . McGraw-Hill , 1966 . Seymour Ginsburg. The mathematical theory of context free languages. McGraw-Hill, 1966."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28729-9_27"},{"key":"e_1_3_2_1_16_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1007\/3-540-60246-1_113","volume-title":"Mathematical Foundations of Computer Science","author":"Gottlob Georg","year":"1995","unstructured":"Georg Gottlob , Nicola Leone , and Helmut Veith . Second order logic and the weak exponential hierarchies . In Ji\u0159\u00ed Wiedermann and Petr H\u00e1jek, editors, Mathematical Foundations of Computer Science , volume 969 of Lecture Notes in Computer Science , pages 66 -- 81 . Springer , 1995 . Georg Gottlob, Nicola Leone, and Helmut Veith. Second order logic and the weak exponential hierarchies. In Ji\u0159\u00ed Wiedermann and Petr H\u00e1jek, editors, Mathematical Foundations of Computer Science, volume 969 of Lecture Notes in Computer Science, pages 66--81. Springer, 1995."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90136-3"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90023-7"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90025-1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90092-6"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80015-2"},{"key":"e_1_3_2_1_22_1","volume-title":"On the estimation of N(σ,T). The Quarterly Journal of Mathematics, os-11(1):201--202","author":"Ingham Albert E.","year":"1940","unstructured":"Albert E. Ingham . On the estimation of N(σ,T). The Quarterly Journal of Mathematics, os-11(1):201--202 , 1940 . Albert E. Ingham. On the estimation of N(σ,T). The Quarterly Journal of Mathematics, os-11(1):201--202, 1940."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1342991.1342995"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1927-04368-3"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1978-0469886-1"},{"key":"e_1_3_2_1_26_1","first-page":"41","volume-title":"Proceedings of the Model Theory Meeting","volume":"33","author":"Lipshitz Leonard M.","year":"1981","unstructured":"Leonard M. Lipshitz . Some remarks on the Diophantine problem for addition and divisibility . In Proceedings of the Model Theory Meeting , volume 33 , pages 41 -- 52 , 1981 . Leonard M. Lipshitz. Some remarks on the Diophantine problem for addition and divisibility. In Proceedings of the Model Theory Meeting, volume 33, pages 41--52, 1981."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1982.11995398"},{"key":"e_1_3_2_1_28_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou . Computational Complexity . Addison-Wesley , 1994 . Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"e_1_3_2_1_30_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-53904-2_94","volume-title":"Rewriting Techniques and Applications","author":"Pottier Lo\u00efc","year":"1991","unstructured":"Lo\u00efc Pottier . Minimal solutions of linear Diophantine systems: bounds and algorithms . In Ronald V. Book, editor, Rewriting Techniques and Applications , volume 488 of Lecture Notes in Computer Science , pages 162 -- 173 . Springer , 1991 . Lo\u00efc Pottier. Minimal solutions of linear Diophantine systems: bounds and algorithms. In Ronald V. Book, editor, Rewriting Techniques and Applications, volume 488 of Lecture Notes in Computer Science, pages 162--173. Springer, 1991."},{"key":"e_1_3_2_1_31_1","first-page":"92","volume-title":"Comptes Rendus du I congres de Mathematiciens des Pays Slaves","author":"Presburger Moj\u017cesz","year":"1929","unstructured":"Moj\u017cesz Presburger . \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 , pages 92 -- 101 . 1929 . Moj\u017cesz Presburger. \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, pages 92--101. 1929."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804361"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0742421-9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679468"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Helmut\n      Seidl Thomas\n      Schwentick Anca\n      Muscholl and \n      Peter\n      Habermehl\n    .\n  Counting in trees for free\n  . In Josep D\u00edaz Juhani Karhum\u00e4ki Arto Lepist\u00f6 and Donald Sannella editors Automata Languages\n   and Programming volume \n  3142\n   of \n  Lecture Notes in Computer Science pages \n  1136\n  --\n  1149\n  . \n  Springer 2004\n  .  Helmut Seidl Thomas Schwentick Anca Muscholl and Peter Habermehl. Counting in trees for free. In Josep D\u00edaz Juhani Karhum\u00e4ki Arto Lepist\u00f6 and Donald Sannella editors Automata Languages and Programming volume 3142 of Lecture Notes in Computer Science pages 1136--1149. Springer 2004.","DOI":"10.1007\/978-3-540-27836-8_94"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11532231_25"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80051-X"},{"issue":"7","key":"e_1_3_2_1_39_1","first-page":"562","article-title":"A circle-of-lights algorithm for the \"money-changing problem","volume":"85","author":"Wilf Herbert S.","year":"1978","unstructured":"Herbert S. Wilf . A circle-of-lights algorithm for the \"money-changing problem \". The American Mathematical Monthly , 85 ( 7 ): 562 -- 565 , 1978 . Herbert S. Wilf. A circle-of-lights algorithm for the \"money-changing problem\". The American Mathematical Monthly, 85(7):562--565, 1978.","journal-title":"The American Mathematical Monthly"},{"key":"e_1_3_2_1_40_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/3-540-60360-3_30","volume-title":"Static Analysis","author":"Wolper Pierre","year":"1995","unstructured":"Pierre Wolper and Bernard Boigelot . An automata-theoretic approach to Presburger arithmetic constraints . In Alan Mycroft, editor, Static Analysis , volume 983 of Lecture Notes in Computer Science , pages 21 -- 32 . Springer , 1995 . Pierre Wolper and Bernard Boigelot. An automata-theoretic approach to Presburger arithmetic constraints. In Alan Mycroft, editor, Static Analysis, volume 983 of Lecture Notes in Computer Science, pages 21--32. Springer, 1995."}],"event":{"name":"CSL-LICS '14: JOINT MEETING OF the Twenty-Third EACSL Annual Conference on COMPUTER SCIENCE LOGIC","location":"Vienna Austria","acronym":"CSL-LICS '14","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2603088.2603092","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2603088.2603092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:33Z","timestamp":1750278153000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2603088.2603092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,14]]},"references-count":40,"alternative-id":["10.1145\/2603088.2603092","10.1145\/2603088"],"URL":"https:\/\/doi.org\/10.1145\/2603088.2603092","relation":{},"subject":[],"published":{"date-parts":[[2014,7,14]]},"assertion":[{"value":"2014-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}