{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:02:54Z","timestamp":1774591374162,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540371878","type":"print"},{"value":"9783540371885","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006]]},"DOI":"10.1007\/11814771_44","type":"book-chapter","created":{"date-parts":[[2006,10,5]],"date-time":"2006-10-05T15:44:21Z","timestamp":1160063061000},"page":"541-556","source":"Crossref","is-referenced-by-count":10,"title":["Presburger Modal Logic Is PSPACE-Complete"],"prefix":"10.1007","author":[{"given":"St\u00e9phane","family":"Demri","sequence":"first","affiliation":[]},{"given":"Denis","family":"Lugiez","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"44_CR1","first-page":"115","volume":"15","author":"L. Afanasiev","year":"2005","unstructured":"Afanasiev, L., Blackburn, P., Dimitriou, I., Gaiffe, B., Goris, E., Marx, M., de Rijke, M.: PDL for ordered trees. JANCL\u00a015(2), 115\u2013135 (2005)","journal-title":"JANCL"},{"issue":"6","key":"44_CR2","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1093\/logcom\/13.6.939","volume":"13","author":"N. Alechina","year":"2003","unstructured":"Alechina, N., Demri, S., de Rijke, M.: A modal perspective on path constraints. JLC\u00a013(6), 939\u2013956 (2003)","journal-title":"JLC"},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1145\/174644.174651","volume":"41","author":"R. Alur","year":"1994","unstructured":"Alur, R., Henzinger, T.: A really temporal logic. JACM\u00a041(1), 181\u2013204 (1994)","journal-title":"JACM"},{"issue":"2","key":"44_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF00379767","volume":"44","author":"M. Fattorosi Barnaba","year":"1985","unstructured":"Fattorosi Barnaba, M., De Caro, F.: Graded modalities. Studia Logica\u00a044(2), 197\u2013221 (1985)","journal-title":"Studia Logica"},{"issue":"4","key":"44_CR5","first-page":"447","volume":"14","author":"N. Bidoit","year":"2004","unstructured":"Bidoit, N., Cerrito, S., Thion, V.: A first step towards modeling semistructured data in hybrid multimodal logic. JANCL\u00a014(4), 447\u2013475 (2004)","journal-title":"JANCL"},{"key":"44_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107050884","volume-title":"Modal Logic","author":"P. Blackburn","year":"2001","unstructured":"Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"44_CR7","first-page":"75","volume":"158","author":"P. Bonatti","year":"2004","unstructured":"Bonatti, P., Peron, A.: On the undecidability of logics with converse, nominals, recursion and counting. AI\u00a0158(1), 75\u201396 (2004)","journal-title":"AI"},{"key":"44_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-540-32033-3_36","volume-title":"Term Rewriting and Applications","author":"I. Boneva","year":"2005","unstructured":"Boneva, I., Talbot, J.M.: Automata and logics for unranked and unordered trees. In: Giesl, J. (ed.) RTA 2005. LNCS, vol.\u00a03467, pp. 500\u2013515. Springer, Heidelberg (2005)"},{"issue":"1","key":"44_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01053022","volume":"53","author":"C. Cerrato","year":"1994","unstructured":"Cerrato, C.: Decidability by filtrations for graded normal logics (graded modalities V). Studia Logica\u00a053(1), 61\u201373 (1994)","journal-title":"Studia Logica"},{"key":"44_CR10","first-page":"178","volume-title":"Description Logics Handbook","author":"D. Calvanese","year":"2005","unstructured":"Calvanese, D., De Giacomo, G.: Expressive description logics. In: Description Logics Handbook, pp. 178\u2013218. Cambridge University Press, Cambridge (2005)"},{"issue":"1\u20133","key":"44_CR11","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/S0304-3975(02)00082-8","volume":"300","author":"S. Demri","year":"2003","unstructured":"Demri, S.: A polynomial space construction of tree-like models for logics with local chains of modal connectives. TCS\u00a0300(1\u20133), 235\u2013258 (2003)","journal-title":"TCS"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Demri, S., Lugiez, D.: Presburger modal logic is PSPACE-complete. Technical report, LSV, ENS de Cachan (2006)","DOI":"10.1007\/11814771_44"},{"issue":"4","key":"44_CR13","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1305\/ndjfl\/1093890715","volume":"13","author":"K. Fine","year":"1972","unstructured":"Fine, K.: In so many possible worlds. NDJFL\u00a013(4), 516\u2013520 (1972)","journal-title":"NDJFL"},{"key":"44_CR14","first-page":"194","volume":"18","author":"M. Fischer","year":"1979","unstructured":"Fischer, M., Ladner, R.: Propositional dynamic logic of regular programs. JCSS\u00a018, 194\u2013211 (1979)","journal-title":"JCSS"},{"key":"44_CR15","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-94-017-1754-0_6","volume-title":"Handbook of Tableaux Methods","author":"R. Gor\u00e9","year":"1999","unstructured":"Gor\u00e9, R.: Tableaux methods for modal and temporal logics. In: Handbook of Tableaux Methods, pp. 297\u2013396. Kluwer Academic Publishers, Dordrecht (1999)"},{"issue":"4","key":"44_CR16","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1093\/logcom\/11.4.609","volume":"11","author":"E. Hemaspaandra","year":"2001","unstructured":"Hemaspaandra, E.: The complexity of poor man\u2019s logic. JLC\u00a011(4), 609\u2013622 (2001)","journal-title":"JLC"},{"key":"44_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/10721959_39","volume-title":"Automated Deduction - CADE-17","author":"I. Horrocks","year":"2000","unstructured":"Horrocks, I., Sattler, U., Tobies, S.: Reasoning with individuals for the description logic SHIQ. In: McAllester, D. (ed.) CADE 2000. LNCS, vol.\u00a01831, pp. 482\u2013496. Springer, Heidelberg (2000)"},{"key":"44_CR18","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/3-540-45620-1_34","volume-title":"Automated Deduction - CADE-18","author":"O. Kupferman","year":"2002","unstructured":"Kupferman, O., Sattler, U., Vardi, M.Y.: The complexity of the graded \u03bc-calculus. In: Voronkov, A. (ed.) CADE 2002. LNCS (LNAI), vol.\u00a02392, pp. 423\u2013437. Springer, Heidelberg (2002)"},{"issue":"3","key":"44_CR19","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0206033","volume":"6","author":"R. Ladner","year":"1977","unstructured":"Ladner, R.: The computational complexity of provability in systems of modal propositional logic. SIAM Journal of Computing\u00a06(3), 467\u2013480 (1977)","journal-title":"SIAM Journal of Computing"},{"key":"44_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-45206-5_13","volume-title":"Automated Reasoning with Analytic Tableaux and Related Methods","author":"M. Marx","year":"2003","unstructured":"Marx, M.: XPath and Modal Logics of finite DAG\u2019s. In: Cialdea Mayer, M., Pirri, F. (eds.) TABLEAUX 2003. LNCS, vol.\u00a02796, pp. 150\u2013164. Springer, Heidelberg (2003)"},{"key":"44_CR21","unstructured":"Montanari, A., Policriti, A.: A set-theoretic approach to automated deduction in graded modal logics. In: IJCAI-15, pp. 196\u2013201 (1997)"},{"key":"44_CR22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-94-017-2798-3_14","volume-title":"Proof theory of modal logic","author":"H.J. Ohlbach","year":"1996","unstructured":"Ohlbach, H.J., Schmidt, R., Hustadt, U.: Translating graded modalities into predicate logics. In: Wansing, H. (ed.) Proof theory of modal logic, pp. 253\u2013291. Kluwer Academic Publishers, Dordrecht (1996)"},{"issue":"4","key":"44_CR23","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"C. Papadimitriou","year":"1981","unstructured":"Papadimitriou, Chr.: On the complexity of integer programming. JACM\u00a028(4), 765\u2013768 (1981)","journal-title":"JACM"},{"key":"44_CR24","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-94-015-8242-1_10","volume-title":"Diamonds and Defaults","author":"E. Spaan","year":"1993","unstructured":"Spaan, E.: The complexity of propositional tense logics. In: de Rijke, M. (ed.) Diamonds and Defaults, pp. 287\u2013309. Kluwer Academic Publishers, Dordrecht (1993)"},{"key":"44_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1007\/978-3-540-27836-8_94","volume-title":"Automata, Languages and Programming","author":"H. Seidl","year":"2004","unstructured":"Seidl, H., Schwentick, Th., Muscholl, A., Habermehl, P.: Counting in trees for free. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1136\u20131149. Springer, Heidelberg (2004), Long version available at (1136) \n                    \n                      http:\/\/www.mathematik.uni-marburg.de\/~tick\/"},{"key":"44_CR26","first-page":"1","volume":"10","author":"S. Tobies","year":"2000","unstructured":"Tobies, S.: PSPACE reasoning for graded modal logics. JLC\u00a010, 1\u201322 (2000)","journal-title":"JLC"},{"issue":"1","key":"44_CR27","first-page":"81","volume":"2","author":"W. Hoek van der","year":"1992","unstructured":"van der Hoek, W.: On the semantics of graded modalities. JANCL\u00a02(1), 81\u2013123 (1992)","journal-title":"JANCL"},{"issue":"3","key":"44_CR28","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1093\/logcom\/5.3.325","volume":"5","author":"W. Hoek van der","year":"1995","unstructured":"van der Hoek, W., de Rijke, M.: Counting objects. JLC\u00a05(3), 325\u2013345 (1995)","journal-title":"JLC"},{"key":"44_CR29","unstructured":"van der Hoek, W., Meyer, J.-J.: Graded modalities in epistemic logic. Logique et Analyse, 133\u2013134, 251\u2013270 (1991)"},{"key":"44_CR30","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/11532231_25","volume-title":"Automated Deduction \u2013 CADE-20","author":"K.N. Verma","year":"2005","unstructured":"Verma, K.N., Seidl, H., Schwentick, Th.: On the complexity of equational Horn clauses. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS (LNAI), vol.\u00a03632, pp. 337\u2013352. Springer, Heidelberg (2005)"},{"key":"44_CR31","first-page":"72","volume":"56","author":"P. Wolper","year":"1983","unstructured":"Wolper, P.: Temporal logic can be more expressive. I & C\u00a056, 72\u201399 (1983)","journal-title":"I & C"},{"key":"44_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/3-540-44881-0_18","volume-title":"Rewriting Techniques and Applications","author":"S. Zilio Dal","year":"2003","unstructured":"Dal Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol.\u00a02706, pp. 246\u2013263. Springer, Heidelberg (2003)"},{"key":"44_CR33","doi-asserted-by":"crossref","unstructured":"Dal Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. Applicable Algebra in Engineering, Communication and Computing (AAECC) (to appear, 2006)","DOI":"10.1007\/s00200-006-0016-7"}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11814771_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T23:34:18Z","timestamp":1558308858000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11814771_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540371878","9783540371885"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11814771_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}