{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T12:14:19Z","timestamp":1753359259976,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662466773"},{"type":"electronic","value":"9783662466780"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46678-0_24","type":"book-chapter","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T09:42:21Z","timestamp":1427881341000},"page":"375-389","source":"Crossref","is-referenced-by-count":2,"title":["On Presburger Arithmetic Extended with Modulo Counting Quantifiers"],"prefix":"10.1007","author":[{"given":"Peter","family":"Habermehl","sequence":"first","affiliation":[]},{"given":"Dietrich","family":"Kuske","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/malq.19660120111","volume":"12","author":"H. Apelt","year":"1966","unstructured":"Apelt, H.: Axiomatische Untersuchungen \u00fcber einige mit der Presburgerschen Arithmetik verwandten Systeme. Z. Math. Logik Grundlagen Math.\u00a012, 131\u2013168 (1966)","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(80)90037-7","volume":"11","author":"L. Berman","year":"1980","unstructured":"Berman, L.: The complexity of logical theories. Theor. Comput. Sci.\u00a011, 71\u201377 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"24_CR3","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00224-004-1133-y","volume":"37","author":"A. Blumensath","year":"2004","unstructured":"Blumensath, A., Gr\u00e4del, E.: Finite presentations of infinite structures: Automata and interpretations. Theory of Computing Systems\u00a037(6), 641\u2013674 (2004)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"24_CR4","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/BF01746527","volume":"3","author":"A. Cobham","year":"1969","unstructured":"Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Mathematical Systems Theory\u00a03(2), 186\u2013192 (1969)","journal-title":"Mathematical Systems Theory"},{"key":"24_CR5","unstructured":"Durand-Gasselin, A., Habermehl, P.: Ehrenfeucht-Fra\u00efss\u00e9 goes elementarily automatic for structures of bounded degree. In: STACS 2012, pp. 242\u2013253. Dagstuhl Publishing (2012)"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-642-15375-4_26","volume-title":"CONCUR 2010 - Concurrency Theory","author":"A. Durand-Gasselin","year":"2010","unstructured":"Durand-Gasselin, A., Habermehl, P.: On the use of non-deterministic automata for Presburger arithmetic. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol.\u00a06269, pp. 373\u2013387. Springer, Heidelberg (2010)"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Ferrante, J., Rackoff, C.W.: The computational complexity of logical theories.. Lecture Notes in Mathematics, vol.\u00a0718, 243 p. Springer, Heidelberg (1979)","DOI":"10.1007\/BFb0062837"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0304-3975(88)90136-3","volume":"56","author":"E. Gr\u00e4del","year":"1988","unstructured":"Gr\u00e4del, E.: Subclasses of Presburger arithmetic and the polynomial-time hierarchy. Theor. Comput. Sci.\u00a056, 289\u2013301 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Haase, C.: Subclasses of Presburger arithmetic and the weak EXP hierarchy. In: CSL-LICS 2014, paper no. 47, 10 pages. ACM (2014)","DOI":"10.1145\/2603088.2603092"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0304-3975(82)90042-1","volume":"19","author":"B.R. Hodgson","year":"1982","unstructured":"Hodgson, B.R.: On direct products of automaton decidable theories. Theoretical Computer Science\u00a019, 331\u2013335 (1982)","journal-title":"Theoretical Computer Science"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/3-540-60178-3_93","volume-title":"Logic and Computational Complexity","author":"B. Khoussainov","year":"1995","unstructured":"Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Leivant, D. (ed.) LCC 1994. LNCS, vol.\u00a0960, pp. 367\u2013392. Springer, Heidelberg (1995)"},{"key":"24_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/978-3-540-24749-4_39","volume-title":"STACS 2004","author":"B. Khoussainov","year":"2004","unstructured":"Khoussainov, B., Rubin, S., Stephan, F.: Definability and regularity in automatic structures. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 440\u2013451. Springer, Heidelberg (2004)"},{"issue":"2","key":"24_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1342991.1342995","volume":"9","author":"F. Klaedtke","year":"2008","unstructured":"Klaedtke, F.: Bounds on the Automata Size for Presburger Arithmetic. ACM Trans. Comput. Logic\u00a09(2), 1\u201334 (2008)","journal-title":"ACM Trans. Comput. Logic"},{"issue":"4","key":"24_CR14","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.2178\/jsl\/1318338854","volume":"76","author":"D. Kuske","year":"2011","unstructured":"Kuske, D., Lohrey, M.: Automatic structures of bounded degree revisited. Journal of Symbolic Logic\u00a076(4), 1352\u20131380 (2011)","journal-title":"Journal of Symbolic Logic"},{"issue":"3","key":"24_CR15","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/j.tcs.2008.09.037","volume":"409","author":"J. Leroux","year":"2008","unstructured":"Leroux, J.: Structural Presburger Digit Vector Automata. Theoretical Computer Science\u00a0409(3), 549\u2013556 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"24_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0022-0000(78)90021-1","volume":"16","author":"D.C. Oppen","year":"1978","unstructured":"Oppen, D.C.: A \n                      \n                        \n                      \n                      $2^{2^{2^{pn}}}$\n                     Upper Bound on the Complexity of Presburger Arithmetic. J. Comput. Syst. Sci.\u00a016(3), 323\u2013332 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR17","unstructured":"Presburger, M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Sprawozdanie z 1 Kongresu Matematyk\u00f3w Krajow Slowia\u0144skich, Ksiaznica Atlas, pp. 92\u2013101. Warzaw (1930)"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Reddy, C.R., Loveland, D.W.: Presburger Arithmetic with Bounded Quantifier Alternation. In: ACM Symposium on Theory of Computing, pp. 320\u2013325 (1978)","DOI":"10.1145\/800133.804361"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2178\/bsl\/1208442827","volume":"14","author":"S. Rubin","year":"2008","unstructured":"Rubin, S.: Automata presenting structures: A survey of the finite string case. Bulletin of Symbolic Logic\u00a014, 169\u2013209 (2008)","journal-title":"Bulletin of Symbolic Logic"},{"issue":"4","key":"24_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02679468","volume":"30","author":"U. Sch\u00f6ning","year":"1997","unstructured":"Sch\u00f6ning, U.: Complexity of Presburger arithmetic with fixed quantifier dimension. Theory Comput. Syst.\u00a030(4), 423\u2013428 (1997)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/1071596.1071602","volume":"6","author":"N. Schweikardt","year":"2005","unstructured":"Schweikardt, N.: Arithmetic, first-order logic, and counting quantifiers. ACM Trans. Comput. Log.\u00a06(3), 634\u2013671 (2005)","journal-title":"ACM Trans. Comput. Log."},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF00967164","volume":"18","author":"A.L. Semenov","year":"1977","unstructured":"Semenov, A.L.: Presburgerness of predicates regular in two number systems. Sib. Math. J.\u00a018, 289\u2013300 (1977)","journal-title":"Sib. Math. J."},{"key":"24_CR23","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1090\/S0002-9939-1978-0500555-0","volume":"72","author":"J. Zur Gathen Von","year":"1978","unstructured":"Von Zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proc. AMS\u00a072, 155\u2013158 (1978)","journal-title":"Proc. AMS"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46678-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T14:32:51Z","timestamp":1559140371000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46678-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662466773","9783662466780"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46678-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}