{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:01:30Z","timestamp":1767927690651,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540875307","type":"print"},{"value":"9783540875314","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87531-4_24","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T08:40:53Z","timestamp":1220085653000},"page":"323-338","source":"Crossref","is-referenced-by-count":15,"title":["On the Almighty Wand"],"prefix":"10.1007","author":[{"given":"R\u00e9mi","family":"Brochenin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Demri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Etienne","family":"Lozes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-30538-5_9","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"J. Berdine","year":"2004","unstructured":"Berdine, J., Calcagno, C., O\u2019Hearn, P.: A decidable fragment of separation logic. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 97\u2013109. Springer, Heidelberg (2004)"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-540-72734-7_8","volume-title":"Logical Foundations of Computer Science","author":"R. Brochenin","year":"2007","unstructured":"Brochenin, R., Demri, S., Lozes, E.: Reasoning about sequences of memory states. In: Artemov, S.N., Nerode, A. (eds.) LFCS 2007. LNCS, vol.\u00a04514, pp. 100\u2013114. Springer, Heidelberg (2007)"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Brochenin, R., Demri, S., Lozes, E.: On the almighty wand. Technical report, LSV, ENS de Cachan (2008)","DOI":"10.1007\/978-3-540-87531-4_24"},{"key":"24_CR4","series-title":"Perspectives in Mathematical Logic","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, Heidelberg (1997)"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-540-31980-1_2","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A. Bouajjani","year":"2005","unstructured":"Bouajjani, A., Habermehl, P., Moro, P., Vojnar, T.: Verifying programs with dynamic 1-selector-linked structured in regular model-checking. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol.\u00a03440, pp. 13\u201329. Springer, Heidelberg (2005)"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1007\/978-3-540-27864-1_25","volume-title":"Static Analysis","author":"M. Bozga","year":"2004","unstructured":"Bozga, M., Iosif, R., Lakhnech, Y.: On logics of aliasing. In: Giacobazzi, R. (ed.) SAS 2004. LNCS, vol.\u00a03148, pp. 344\u2013360. Springer, Heidelberg (2004)"},{"key":"24_CR7","unstructured":"Bozga, M., Iosif, R., Perarnau, S.: Quantitative separation logic and programs with lists. In: IJCAR 2008 (to appear, 2008)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/978-3-540-31982-5_25","volume-title":"Foundations of Software Science and Computational Structures","author":"C. Calcagno","year":"2005","unstructured":"Calcagno, C., Gardner, P., Hague, M.: From separation logic to first-order logic. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol.\u00a03441, pp. 395\u2013409. Springer, Heidelberg (2005)"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Calcagno, C., Yang, H., O\u2019Hearn, P.: Computability and complexity results for a spatial assertion language. In: APLAS 2001, pp. 289\u2013300 (2001)","DOI":"10.1007\/3-540-45294-X_10"},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-45294-X_10","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"C. Calcagno","year":"2001","unstructured":"Calcagno, C., Yang, H., O\u2019Hearn, P.: Computability and complexity results for a spatial assertion language for data structures. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 108\u2013119. Springer, Heidelberg (2001)"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-540-30538-5_18","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"A. Dawar","year":"2004","unstructured":"Dawar, A., Gardner, P., Ghelli, G.: Adjunct elimination through games in static ambient logic. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 211\u2013223. Springer, Heidelberg (2004)"},{"issue":"3","key":"24_CR12","first-page":"263","volume":"205","author":"A. Dawar","year":"2007","unstructured":"Dawar, A., Gardner, P., Ghelli, G.: Expressiveness and complexity of graph logic. I & C\u00a0205(3), 263\u2013310 (2007)","journal-title":"I & C"},{"key":"24_CR13","unstructured":"Galmiche, D., M\u00e9ry, D.: Tableaux and resource graphs for separation logic (submitted, 2008)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Ishtiaq, S., O\u2019Hearn, P.: BI as an assertion language for mutable data structures. In: POPL 2001, pp. 14\u201326 (2001)","DOI":"10.1145\/373243.375719"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1145\/258915.258936","volume-title":"PLDI 1997","author":"J. Jensen","year":"1997","unstructured":"Jensen, J., Jorgensen, M., Klarlund, N., Schwartzbach, M.: Automatic verification of pointer programs using monadic second-order logic. In: PLDI 1997, pp. 226\u2013236. ACM, New York (1997)"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/3-540-45061-0_54","volume-title":"Automata, Languages and Programming","author":"F. Klaedtke","year":"2003","unstructured":"Klaedtke, F., Rueb, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 681\u2013696. Springer, Heidelberg (2003)"},{"key":"24_CR17","unstructured":"Kuncak, V., Rinard, M.: On spatial conjunction as second-order logic. Technical report, MIT CSAIL (October 2004)"},{"key":"24_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/978-3-540-45099-3_15","volume-title":"Static Analysis","author":"T. Lev-Ami","year":"2000","unstructured":"Lev-Ami, T., Sagiv, M.: TVLA: A system for implementing static analyses. In: Palsberg, J. (ed.) SAS 2000. LNCS, vol.\u00a01824, pp. 280\u2013302. Springer, Heidelberg (2000)"},{"key":"24_CR19","unstructured":"Lozes, E.: Separation logic preserves the expressive power of classical logic. In: 2nd Workshop on Semantics, Program Analysis, and Computing Environments for Memory Management (SPACE 2004) (2004)"},{"issue":"3","key":"24_CR20","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1016\/j.tcs.2004.10.006","volume":"330","author":"E. Lozes","year":"2005","unstructured":"Lozes, E.: Elimination of spatial connectives in static spatial logics. TCS\u00a0330(3), 475\u2013499 (2005)","journal-title":"TCS"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/978-3-540-24597-1_26","volume-title":"FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science","author":"C. L\u00f6ding","year":"2003","unstructured":"L\u00f6ding, C., Rohde, P.: Model checking and satisfiability for sabotage modal logic. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol.\u00a02914, pp. 302\u2013313. Springer, Heidelberg (2003)"},{"key":"24_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/11874683_32","volume-title":"Computer Science Logic","author":"J. Marcinkowski","year":"2006","unstructured":"Marcinkowski, J.: On the expressive power of graph logic. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 486\u2013500. Springer, Heidelberg (2006)"},{"key":"24_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-74061-2_26","volume-title":"Static Analysis","author":"S. Magill","year":"2007","unstructured":"Magill, S., Berdine, J., Clarke, E., Cook, B.: Arithmetic strengthening for shape analysis. In: Riis Nielson, H., Fil\u00e9, G. (eds.) SAS 2007. LNCS, vol.\u00a04634, pp. 419\u2013436. Springer, Heidelberg (2007)"},{"key":"24_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"41","author":"M. Rabin","year":"1969","unstructured":"Rabin, M.: Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society\u00a041, 1\u201335 (1969)","journal-title":"Transactions of the American Mathematical Society"},{"key":"24_CR25","first-page":"55","volume-title":"LICS 2002","author":"J.C. Reynolds","year":"2002","unstructured":"Reynolds, J.C.: Separation logic: a logic for shared mutable data structures. In: LICS 2002, pp. 55\u201374. IEEE, Los Alamitos (2002)"},{"key":"24_CR26","first-page":"206","volume-title":"SEFM 2006","author":"S. Ranise","year":"2006","unstructured":"Ranise, S., Zarba, C.: A theory of singly-linked lists and its extensible decision procedure. In: SEFM 2006, pp. 206\u2013215. IEEE, Los Alamitos (2006)"},{"key":"24_CR27","unstructured":"Stockmeyer, L.: The complexity of decision problems in automata theory and logic. PhD thesis, Department of Electrical Engineering. MIT (1974)"},{"key":"24_CR28","first-page":"566","volume":"70","author":"B.A. Trakhtenbrot","year":"1950","unstructured":"Trakhtenbrot, B.A.: The impossibility of an algorithm for the decision problem for finite models. Dokl. Akad. Nauk SSSR\u00a070, 566\u2013572 (1950); English translation in: AMS Transl. Ser. 2, 23(1063), 1\u20136","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"24_CR29","series-title":"Lecture Notes in Computer Science","first-page":"94","volume-title":"Foundations of Software Science and Computational Structures","author":"G. Yorsh","year":"2005","unstructured":"Yorsh, G., Rabinovich, A.M., Sagiv, M., Meyer, A., Bouajjani, A.: A logic of reachable patterns in linked data structures. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol.\u00a03441, pp. 94\u2013110. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87531-4_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:04:37Z","timestamp":1738350277000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87531-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540875307","9783540875314"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87531-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}