{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T07:42:37Z","timestamp":1768290157755,"version":"3.49.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031661488","type":"print"},{"value":"9783031661495","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-66149-5_7","type":"book-chapter","created":{"date-parts":[[2024,10,12]],"date-time":"2024-10-12T07:01:54Z","timestamp":1728716514000},"page":"137-145","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Random Access on\u00a0Narrow Decision Diagrams in\u00a0External Memory"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0963-6569","authenticated-orcid":false,"given":"Steffan Christ","family":"S\u00f8lvsten","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3989-123X","authenticated-orcid":false,"given":"Casper Moldrup","family":"Rysgaard","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4305-0625","authenticated-orcid":false,"given":"Jaco","family":"Van\u00a0de\u00a0Pol","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,13]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","unstructured":"Aggarwal, A., Vitter, Jeffrey, S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988). https:\/\/doi.org\/10.1145\/48529.48535","DOI":"10.1145\/48529.48535"},{"key":"7_CR2","unstructured":"Amar\u00fa, L., Gaillardon, P.E., De\u00a0Micheli, G.: The EPFL combinational benchmark suite. In: 24th International Workshop on Logic and Synthesis (2015)"},{"key":"7_CR3","doi-asserted-by":"publisher","unstructured":"Arge, L.: The buffer tree: a new technique for optimal I\/O-algorithms. In: Workshop on Algorithms and Data Structures (WADS). LNCS, vol.\u00a0955, pp. 334\u2013345. Springer, Heidelberg (1995).https:\/\/doi.org\/10.1007\/3-540-60220-8_74","DOI":"10.1007\/3-540-60220-8_74"},{"key":"7_CR4","doi-asserted-by":"publisher","unstructured":"Arge, L.: The I\/O-complexity of ordered binary-decision diagram manipulation. In: 6th International Symposium on Algorithms and Computations (ISAAC). LNCS, vol.\u00a01004, pp. 82\u201391 (1995). https:\/\/doi.org\/10.1007\/BFb0015411","DOI":"10.1007\/BFb0015411"},{"key":"7_CR5","doi-asserted-by":"publisher","unstructured":"Arge, L.: The I\/O-complexity of ordered binary-decision diagram. In: BRICS RS Preprint Series, vol.\u00a029. Department of Computer Science, University of Aarhus (1996). https:\/\/doi.org\/10.7146\/brics.v3i29.20010","DOI":"10.7146\/brics.v3i29.20010"},{"key":"7_CR6","doi-asserted-by":"publisher","unstructured":"Ashar, P., Cheong, M.: Efficient breadth-first manipulation of binary decision diagrams. In: IEEE\/ACM International Conference on Computer-Aided Design (ICCAD), pp. 622\u2013627. IEEE Computer Society Press (1994). https:\/\/doi.org\/10.1109\/ICCAD.1994.629886","DOI":"10.1109\/ICCAD.1994.629886"},{"key":"7_CR7","doi-asserted-by":"publisher","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35(8), 677\u2013691 (1986). https:\/\/doi.org\/10.1109\/TC.1986.1676819","DOI":"10.1109\/TC.1986.1676819"},{"key":"7_CR8","unstructured":"Chiang, Y.J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), pp. 139\u2014149. Society for Industrial and Applied Mathematics (1995)"},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Elgaard, J., Klarlund, N., M\u00f8ller, A.: MONA 1.x: new techniques for WS1S and WS2S. In: Proceedings of the 10th International Conference on Computer-Aided Verification, CAV 1998. LNCS, vol.\u00a01427, pp. 516\u2013520. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-61648-9_56","DOI":"10.1007\/3-540-61648-9_56"},{"key":"7_CR10","doi-asserted-by":"publisher","unstructured":"Kant, G., Laarman, A., Meijer, J., Van de Pol, J., Blom, S., Van Dijk, T.: LTSmin: high-performance language-independent model checking. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS). LNCS, vol.\u00a09035, pp. 692\u2013707. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46681-0_61","DOI":"10.1007\/978-3-662-46681-0_61"},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Klarlund, N.: Mona & Fido: the logic-automaton connection in practice. In: Computer Science Logic. LNCS, vol.\u00a01414, pp. 311\u2013326. Springer, Cham (1998). https:\/\/doi.org\/10.1007\/BFb0028022","DOI":"10.1007\/BFb0028022"},{"key":"7_CR12","doi-asserted-by":"publisher","unstructured":"Klarlund, N., Rauhe, T.: BDD algorithms and cache misses. In: BRICS Report Series, vol.\u00a026 (1996). https:\/\/doi.org\/10.7146\/brics.v3i26.20007","DOI":"10.7146\/brics.v3i26.20007"},{"key":"7_CR13","doi-asserted-by":"publisher","unstructured":"Larsen, C.A., Schmidt, S.M., Steensgaard, J., Jakobsen, A.B., van\u00a0de Pol, J., Pavlogiannis, A.: A truly symbolic linear-time algorithm for SCC decomposition. In: Tools and Algorithms for the Construction and Analysis of Systems (2). LNCS, vol. 13994, pp. 353\u2013371. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-30820-8_22","DOI":"10.1007\/978-3-031-30820-8_22"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Long, D.E.: The design of a cache-friendly BDD library. In: Proceedings of the 1998 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD), pp. 639\u2013645. Association for Computing Machinery (1998)","DOI":"10.1145\/288548.289102"},{"key":"7_CR15","doi-asserted-by":"publisher","unstructured":"Meyer, U., Sanders, P., Sibeyn, J.: Algorithms for Memory Hierarchies: Advanced Lectures. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36574-5","DOI":"10.1007\/3-540-36574-5"},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"Minato, S.I., Ishiura, N., Yajima, S.: Shared binary decision diagram with attributed edges for efficient Boolean function manipulation. In: 27th Design Automation Conference (DAC), pp. 52\u201357. Association for Computing Machinery (1990). https:\/\/doi.org\/10.1145\/123186.123225","DOI":"10.1145\/123186.123225"},{"key":"7_CR17","doi-asserted-by":"publisher","unstructured":"Ochi, H., Yasuoka, K., Yajima, S.: Breadth-first manipulation of very large binary-decision diagrams. In: International Conference on Computer Aided Design (ICCAD), pp. 48\u201355. IEEE Computer Society Press (1993). https:\/\/doi.org\/10.1109\/ICCAD.1993.580030","DOI":"10.1109\/ICCAD.1993.580030"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/3-540-58152-9_23","volume-title":"Application and Theory of Petri Nets 1994","author":"E Pastor","year":"1994","unstructured":"Pastor, E., Roig, O., Cortadella, J., Badia, R.M.: Petri net analysis using boolean manipulation. In: Valette, R. (ed.) ICATPN 1994. LNCS, vol. 815, pp. 416\u2013435. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58152-9_23"},{"key":"7_CR19","unstructured":"Pastva, S., Henzinger, T.: Binary decision diagrams on modern hardware. In: Conference on Formal Methods in Computer-Aided Design, pp. 122\u2013131 (2023)"},{"key":"7_CR20","doi-asserted-by":"publisher","unstructured":"Sanghavi, J.V., Ranjan, R.K., Brayton, R.K., Sangiovanni-Vincentelli, A.: High performance BDD package by exploiting memory hierarchy. In: 33rd Design Automation Conference (DAC), pp. 635\u2013640. Association for Computing Machinery (1996). https:\/\/doi.org\/10.1145\/240518.240638","DOI":"10.1145\/240518.240638"},{"key":"7_CR21","doi-asserted-by":"publisher","unstructured":"S\u00f8lvsten, S.C., Van de Pol, J.: Predicting memory demands of BDD operations using maximum graph cuts. In: Andr\u00e9, \u00c9., Sun, J. (eds.) Automated Technology for Verification and Analysis. LNCS, vol. 14216, pp. 72\u201392. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-45332-8_4","DOI":"10.1007\/978-3-031-45332-8_4"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"S\u00f8lvsten, S.C., Van de Pol, J.: Adiar 1.1: zero-suppressed decision diagrams in external memory. In: NASA Formal Methods Symposium, LNCS, vol. 13903, Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-33170-1_28","DOI":"10.1007\/978-3-031-33170-1_28"},{"key":"7_CR23","unstructured":"S\u00f8lvsten, S.C., Van de Pol, J., Jakobsen, A.B., Thomasen, M.W.B.: Efficient binary decision diagram manipulation in external memory. arXiv preprint arXiv:2104.12101 (2021)"},{"key":"7_CR24","doi-asserted-by":"publisher","unstructured":"S\u00f8lvsten, S.C., Van de Pol, J., Jakobsen, A.B., Thomasen, M.W.B.: Adiar: binary decision diagrams in external memory. In: Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 13244, pp. 295\u2013313. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-030-99527-0_16","DOI":"10.1007\/978-3-030-99527-0_16"},{"key":"7_CR25","doi-asserted-by":"publisher","unstructured":"S\u00f8lvsten, S.C., Rysgaard, C.M., van de Pol, J.: Adiar 2.0.0-beta.3 : Experiment Data (2024). https:\/\/doi.org\/10.5281\/zenodo.10493770","DOI":"10.5281\/zenodo.10493770"},{"key":"7_CR26","unstructured":"Somenzi, F.: CUDD: CU decision diagram package, 3.0. Tech. rep., University of Colorado at Boulder (2015)"},{"key":"7_CR27","doi-asserted-by":"publisher","unstructured":"Slvsten, S.C.: BDD Benchmark. Zenodo (2024).https:\/\/doi.org\/10.5281\/zenodo.10803154","DOI":"10.5281\/zenodo.10803154"}],"container-title":["Lecture Notes in Computer Science","Model Checking Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-66149-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,12]],"date-time":"2024-10-12T07:06:06Z","timestamp":1728716766000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-66149-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,13]]},"ISBN":["9783031661488","9783031661495"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-66149-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,13]]},"assertion":[{"value":"13 October 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The data presented in Sect.\u00a0 is available\u00a0at [] while the code to run the benchmarks can be found\u00a0at [].","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Data Availability Statement"}},{"value":"SPIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Model Checking Software","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spin2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/spin-web.github.io\/SPIN2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}