{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T02:05:55Z","timestamp":1776305155652,"version":"3.50.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032087065","type":"print"},{"value":"9783032087072","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T00:00:00Z","timestamp":1761436800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T00:00:00Z","timestamp":1761436800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-08707-2_20","type":"book-chapter","created":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T22:33:34Z","timestamp":1761431614000},"page":"425-446","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Data Structures for\u00a0Finite Downsets of\u00a0Natural Vectors: Theory and\u00a0Practice"],"prefix":"10.1007","author":[{"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[]},{"given":"Vanessa","family":"Fl\u00fcgel","sequence":"additional","affiliation":[]},{"given":"Guillermo A.","family":"P\u00e9rez","sequence":"additional","affiliation":[]},{"given":"Shrisha","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,26]]},"reference":[{"key":"20_CR1","unstructured":"Baier, C., Katoen, J.: Principles of Model Checking. MIT Press (2008)"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer (2008). https:\/\/www.worldcat.org\/oclc\/227584184","DOI":"10.1007\/978-3-540-77974-2"},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1051\/ITA:2002013","volume":"36","author":"J Bernet","year":"2002","unstructured":"Bernet, J., Janin, D., Walukiewicz, I.: Permissive strategies: from parity games to safety games. RAIRO Theor. Informatics Appl. 36(3), 261\u2013275 (2002). https:\/\/doi.org\/10.1051\/ITA:2002013","journal-title":"RAIRO Theor. Informatics Appl."},{"issue":"10","key":"20_CR4","doi-asserted-by":"publisher","first-page":"1206","DOI":"10.1016\/j.ic.2009.09.006","volume":"208","author":"D Berwanger","year":"2010","unstructured":"Berwanger, D., Chatterjee, K., Wulf, M.D., Doyen, L., Henzinger, T.A.: Strategy construction for parity games with imperfect information. Inf. Comput. 208(10), 1206\u20131220 (2010)","journal-title":"Inf. Comput."},{"key":"20_CR5","first-page":"12","volume":"21","author":"A Blumer","year":"1983","unstructured":"Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., McConnell, R.M.: Linear size finite automata for the set of all subwords of a word - an outline of results. Bull. EATCS 21, 12\u201320 (1983)","journal-title":"Bull. EATCS"},{"key":"20_CR6","doi-asserted-by":"publisher","unstructured":"Brass, P.: Advanced Data Structures. Cambridge University Press (2008). https:\/\/doi.org\/10.1017\/CBO9780511800191","DOI":"10.1017\/CBO9780511800191"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-031-30820-8_14","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M Cadilhac","year":"2023","unstructured":"Cadilhac, M., P\u00e9rez, G.A.: Acacia-bonsai: a modern implementation of downset-based LTL realizability. In: Sankaranarayanan, S., Sharygina, N. (eds.) TACAS 2023. LNCS, vol. 13994, pp. 192\u2013207. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30820-8_14"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1007\/S00454-019-00062-5","volume":"61","author":"TM Chan","year":"2019","unstructured":"Chan, T.M.: Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back. Discret. Comput. Geom. 61(4), 899\u2013922 (2019). https:\/\/doi.org\/10.1007\/S00454-019-00062-5","journal-title":"Discret. Comput. Geom."},{"key":"20_CR9","doi-asserted-by":"publisher","unstructured":"Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R. (eds.): Handbook of Model Checking. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-10575-8","DOI":"10.1007\/978-3-319-10575-8"},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1162\/089120100561601","volume":"26","author":"J Daciuk","year":"2000","unstructured":"Daciuk, J., Mihov, S., Watson, B.W., Watson, R.E.: Incremental construction of minimal acyclic finite state automata. Comput. Linguist. 26(1), 3\u201316 (2000). https:\/\/doi.org\/10.1162\/089120100561601","journal-title":"Comput. Linguist."},{"issue":"3","key":"20_CR11","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1137\/070697720","volume":"40","author":"C Daskalakis","year":"2011","unstructured":"Daskalakis, C., Karp, R.M., Mossel, E., Riesenfeld, S.J., Verbin, E.: Sorting and selection in posets. SIAM J. Comput. 40(3), 597\u2013622 (2011). https:\/\/doi.org\/10.1137\/070697720","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"20_CR12","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/S10009-003-0110-0","volume":"5","author":"G Delzanno","year":"2004","unstructured":"Delzanno, G., Raskin, J., Begin, L.V.: Covering sharing trees: a compact data structure for parameterized verification. Int. J. Softw. Tools Technol. Transf. 5(2\u20133), 268\u2013297 (2004). https:\/\/doi.org\/10.1007\/S10009-003-0110-0","journal-title":"Int. J. Softw. Tools Technol. Transf."},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-319-89960-2_16","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Dijk","year":"2018","unstructured":"Dijk, T.: Oink: an implementation and evaluation of modern parity game solvers. In: Beyer, D., Huisman, M. (eds.) TACAS 2018. LNCS, vol. 10805, pp. 291\u2013308. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89960-2_16"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-031-57246-3_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Dijk","year":"2024","unstructured":"Dijk, T., Abbema, F., Tomov, N.: Knor: reactive synthesis using oink. In: Finkbeiner, B., Kov\u00e1cs, L. (eds.) TACAS 2024, Part I. LNCS, vol. 14570, pp. 103\u2013122. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-57246-3_7"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-031-30823-9_15","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"K Doveri","year":"2023","unstructured":"Doveri, K., Ganty, P., Hadzi-Dokic, L.: Antichains algorithms for the inclusion problem between omega-VPL. In: Sankaranarayanan, S., Sharygina, N. (eds.) TACAS 2023. LNCS, vol. 13993, pp. 290\u2013307. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30823-9_15"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Doyen, L., Raskin, J.: Antichains for the automata-based approach to model-checking. Log. Methods Comput. Sci. 5(1) (2009)","DOI":"10.2168\/LMCS-5(1:5)2009"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Doyen, L., Raskin, J.: Games with imperfect information: theory and algorithms. In: Lectures in Game Theory for Computer Scientists, pp. 185\u2013212. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511973468.007"},{"key":"20_CR18","unstructured":"Falgas-Ravry, V., R\u00e4ty, E., Tomon, I.: Dedekind\u2019s problem in the hypergrid (2023). https:\/\/arxiv.org\/abs\/2310.12946"},{"issue":"3","key":"20_CR19","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10703-011-0115-3","volume":"39","author":"E Filiot","year":"2011","unstructured":"Filiot, E., Jin, N., Raskin, J.: Antichains and compositional algorithms for LTL synthesis. Formal Methods Syst. Des. 39(3), 261\u2013296 (2011)","journal-title":"Formal Methods Syst. Des."},{"key":"20_CR20","unstructured":"Ganty, P.: Algorithmes et structures de donn\u00e9es efficaces pour la manipulation de contraintes sur les intervalles (in French). Master\u2019s thesis, Universit\u00e9 Libre de Bruxelles, Belgium (2002)"},{"key":"20_CR21","unstructured":"Ganty, P., Meuter, C., Delzanno, G., Kalyon, G., Raskin, J., Van Begin, L.: Symbolic data structure for sets of k-uples. Technical report 570, Universit\u00e9 Libre de Bruxelles, Belgium (2007)"},{"issue":"3","key":"20_CR22","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10703-020-00345-1","volume":"55","author":"L Hol\u00edk","year":"2020","unstructured":"Hol\u00edk, L., Iosif, R., Rogalewicz, A., Vojnar, T.: Abstraction refinement and antichains for trace inclusion of infinite state systems. Formal Methods Syst. Design 55(3), 137\u2013170 (2020). https:\/\/doi.org\/10.1007\/s10703-020-00345-1","journal-title":"Formal Methods Syst. Design"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/3-540-44977-9_31","volume-title":"Implementation and Application of Automata","author":"J Holub","year":"2003","unstructured":"Holub, J., Crochemore, M.: On the implementation of compact DAWG\u2019s. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 289\u2013294. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44977-9_31"},{"issue":"8","key":"20_CR24","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/s00236-017-0304-7","volume":"55","author":"P Hunter","year":"2018","unstructured":"Hunter, P., P\u00e9rez, G.A., Raskin, J.: Looking at mean payoff through foggy windows. Acta Inform. 55(8), 627\u2013647 (2018)","journal-title":"Acta Inform."},{"issue":"5","key":"20_CR25","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/S10009-024-00754-1","volume":"26","author":"S Jacobs","year":"2024","unstructured":"Jacobs, S., et al.: The reactive synthesis competition (SYNTCOMP): 2018\u20132021. Int. J. Softw. Tools Technol. Transf. 26(5), 551\u2013567 (2024). https:\/\/doi.org\/10.1007\/S10009-024-00754-1","journal-title":"Int. J. Softw. Tools Technol. Transf."},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-24644-4_9","volume-title":"Fundamentals of Software Engineering","author":"JJA Keiren","year":"2015","unstructured":"Keiren, J.J.A.: Benchmarks for parity games. In: Dastani, M., Sirjani, M. (eds.) FSEN 2015. LNCS, vol. 9392, pp. 127\u2013142. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24644-4_9"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Laveaux, M., Groote, J.F., Willemse, T.A.C.: Correct and efficient antichain algorithms for refinement checking. Log. Methods Comput. Sci. 17(1) (2021). https:\/\/lmcs.episciences.org\/7143","DOI":"10.23638\/LMCS-17(1:8)2021"},{"key":"20_CR28","doi-asserted-by":"publisher","unstructured":"Micha\u00ebl\u00a0Cadilhac, Vanessa\u00a0Fl\u00fcgel, G.A.P.: Code for data structures for finite downsets of natural vectors (2025). https:\/\/doi.org\/10.5281\/zenodo.15837722","DOI":"10.5281\/zenodo.15837722"},{"issue":"1","key":"20_CR29","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D Revuz","year":"1992","unstructured":"Revuz, D.: Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci. 92(1), 181\u2013189 (1992). https:\/\/doi.org\/10.1016\/0304-3975(92)90142-3","journal-title":"Theor. Comput. Sci."},{"key":"20_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-34281-3_26","volume-title":"Formal Methods and Software Engineering","author":"T Wang","year":"2012","unstructured":"Wang, T., et al.: More anti-chain based refinement checking. In: Aoki, T., Taguchi, K. (eds.) ICFEM 2012. LNCS, vol. 7635, pp. 364\u2013380. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34281-3_26"},{"key":"20_CR31","unstructured":"Zampuni\u00e9ris, D.: The sharing tree data structure, theory and applications in formal verification. Ph.D. thesis, Department of Computer Science, University of Namur, Belgium (1997)"}],"container-title":["Lecture Notes in Computer Science","Automated Technology for Verification and Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-08707-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T22:33:38Z","timestamp":1761431618000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-08707-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,26]]},"ISBN":["9783032087065","9783032087072"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-08707-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,26]]},"assertion":[{"value":"26 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ATVA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Automated Technology for Verification and Analysis","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bengaluru","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 October 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 October 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"atva2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.researchr.org\/home\/atva-2025","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}