{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:59:22Z","timestamp":1775818762806,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005005","name":"Ben-Gurion University of the Negev","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1101\/07"],"award-info":[{"award-number":["1101\/07"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000935","name":"Department of Broadband, Communications and the Digital Economy , Australian Government","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000935","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012950","name":"INRIA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>\n            Many areas of computer science require answering questions about reachability in compactly described discrete transition systems. Answering such questions effectively requires techniques to be able to do so without building the entire system. In particular, heuristic search uses lower-bounding (\u201cadmissible\u201d) heuristic functions to prune parts of the system known to not contain an optimal solution. A prominent technique for deriving such bounds is to consider abstract transition systems that aggregate groups of states into one. The key question is how to design and represent such abstractions. The most successful answer to this question are pattern databases, which aggregate states if and only if they agree on a subset of the state variables.\n            <jats:italic>Merge-and-shrink abstraction<\/jats:italic>\n            is a new paradigm that, as we show, allows to compactly represent a more general class of abstractions, strictly dominating pattern databases in theory. We identify the maximal class of transition systems, which we call\n            <jats:italic>factored transition systems<\/jats:italic>\n            , to which merge-and-shrink applies naturally, and we show that the well-known notion of bisimilarity can be adapted to this framework in a way that still guarantees perfect heuristic functions, while potentially reducing abstraction size exponentially. Applying these ideas to planning, one of the foundational subareas of artificial intelligence, we show that in some benchmarks this size reduction leads to the computation of perfect heuristic functions in polynomial time and that more approximate merge-and-shrink strategies yield heuristic functions competitive with the state of the art.\n          <\/jats:p>","DOI":"10.1145\/2559951","type":"journal-article","created":{"date-parts":[[2014,5,27]],"date-time":"2014-05-27T12:56:59Z","timestamp":1401195419000},"page":"1-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Merge-and-Shrink Abstraction"],"prefix":"10.1145","volume":"61","author":[{"given":"Malte","family":"Helmert","sequence":"first","affiliation":[{"name":"University of Basel, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrik","family":"Haslum","sequence":"additional","affiliation":[{"name":"The Australian National University and NICTA, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Hoffmann","sequence":"additional","affiliation":[{"name":"Saarland University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raz","family":"Nissim","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1995.tb00052.x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/259794.259826"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08)","author":"Ball Marcel","unstructured":"Marcel Ball and Robert C. Holte . 2008. The compression power of symbolic pattern databases , In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08) . Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, Eds., AAAI Press, 2--11. Marcel Ball and Robert C. Holte. 2008. The compression power of symbolic pattern databases, In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08). Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, Eds., AAAI Press, 2--11."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS'05)","author":"Boddy Mark","year":"2005","unstructured":"Mark Boddy , Johnathan Gohde , Tom Haigh , and Steven Harp . 2005 . Course of action generation for cyber security using classical planning . In Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS'05) . Susanne Biundo, Karen Myers, and Kanna Rajan, Eds., AAAI Press, 12--21. Mark Boddy, Johnathan Gohde, Tom Haigh, and Steven Harp. 2005. Course of action generation for cyber security using classical planning. In Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS'05). Susanne Biundo, Karen Myers, and Kanna Rajan, Eds., AAAI Press, 12--21."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90081-7"},{"key":"e_1_2_1_6_1","volume-title":"Peled","author":"Clarke Edmund M.","year":"2000","unstructured":"Edmund M. Clarke , Orna Grumberg , and Doron A . Peled . 2000 . Model Checking. The MIT Press . Edmund M. Clarke, Orna Grumberg, and Doron A. Peled. 2000. Model Checking. The MIT Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/0824-7935.00065"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622810.1622817"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3830"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08)","author":"Do Minh B.","year":"2008","unstructured":"Minh B. Do , Wheeler Ruml , and Rong Zhou . 2008 . Planning for modular printers: Beyond productivity , In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08) . Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, Eds., AAAI Press 68--75. Minh B. Do, Wheeler Ruml, and Rong Zhou. 2008. Planning for modular printers: Beyond productivity, In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08). Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, Eds., AAAI Press 68--75."},{"key":"e_1_2_1_13_1","volume-title":"IPC 2011 Planner Abstracts, 91--95","author":"Domshlak Carmel","year":"2011","unstructured":"Carmel Domshlak , Malte Helmert , Erez Karpas , Emil Keyder , Silvia Richter , Gabriele R\u00f6ger , Jendrik Seipp , and Matthias Westphal . 2011 . BJOLP: The big joint optimal landmarks planner . In IPC 2011 Planner Abstracts, 91--95 . Carmel Domshlak, Malte Helmert, Erez Karpas, Emil Keyder, Silvia Richter, Gabriele R\u00f6ger, Jendrik Seipp, and Matthias Westphal. 2011. BJOLP: The big joint optimal landmarks planner. In IPC 2011 Planner Abstracts, 91--95."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11691617_2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-008-0092-z"},{"key":"e_1_2_1_16_1","volume-title":"Pre-proceedings of the 6th European Conference on Planning (ECP'01)","author":"Edelkamp Stefan","year":"2001","unstructured":"Stefan Edelkamp . 2001 . Planning with pattern databases . In Pre-proceedings of the 6th European Conference on Planning (ECP'01) . Amedeo Cesta and Daniel Borrajo, Eds., 13--24. Stefan Edelkamp. 2001. Planning with pattern databases. In Pre-proceedings of the 6th European Conference on Planning (ECP'01). Amedeo Cesta and Daniel Borrajo, Eds., 13--24."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'02)","author":"Edelkamp Stefan","year":"2002","unstructured":"Stefan Edelkamp . 2002 . Symbolic pattern databases in heuristic search planning . In Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'02) . Malik Ghallab, Joachim Hertzberg, and Paolo Traverso, Eds., AAAI Press, 274--283. Stefan Edelkamp. 2002. Symbolic pattern databases in heuristic search planning. In Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'02). Malik Ghallab, Joachim Hertzberg, and Paolo Traverso, Eds., AAAI Press, 274--283."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1767111.1767124"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622487.1622496"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(71)90010-5"},{"key":"e_1_2_1_21_1","volume-title":"Automated Planning: Theory and Practice. Morgan Kaufmann.","author":"Ghallab Malik","year":"2004","unstructured":"Malik Ghallab , Dana Nau , and Paolo Traverso . 2004 . Automated Planning: Theory and Practice. Morgan Kaufmann. Malik Ghallab, Dana Nau, and Paolo Traverso. 2004. Automated Planning: Theory and Practice. Morgan Kaufmann."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05)","author":"Haslum Patrik","year":"2005","unstructured":"Patrik Haslum , Blai Bonet , and H\u00e9ctor Geffner . 2005 . New admissible heuristics for domain-independent planning . In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05) . AAAI Press, 1163--1168. Patrik Haslum, Blai Bonet, and H\u00e9ctor Geffner. 2005. New admissible heuristics for domain-independent planning. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05). AAAI Press, 1163--1168."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07)","author":"Haslum Patrik","year":"2007","unstructured":"Patrik Haslum , Adi Botea , Malte Helmert , Blai Bonet , and Sven Koenig . 2007 . Domain-independent construction of pattern database heuristics for cost-optimal planning . In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07) . AAAI Press, 1007--1012. Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet, and Sven Koenig. 2007. Domain-independent construction of pattern database heuristics for cost-optimal planning. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI'07). AAAI Press, 1007--1012."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00)","author":"Haslum Patrik","year":"2000","unstructured":"Patrik Haslum and H\u00e9ctor Geffner . 2000 . Admissible heuristics for optimal planning . In Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00) . Steve Chien, Subbarao Kambhampati, and Craig A. Knoblock, Eds., AAAI Press, 140--149. Patrik Haslum and H\u00e9ctor Geffner. 2000. Admissible heuristics for optimal planning. In Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00). Steve Chien, Subbarao Kambhampati, and Craig A. Knoblock, Eds., AAAI Press, 140--149."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS'04)","author":"Helmert Malte","year":"2004","unstructured":"Malte Helmert . 2004 . A planning heuristic based on causal graph analysis . In Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS'04) . Shlomo Zilberstein, Jana Koehler, and Sven Koenig, Eds., AAAI Press, 161--170. Malte Helmert. 2004. A planning heuristic based on causal graph analysis. In Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS'04). Shlomo Zilberstein, Jana Koehler, and Sven Koenig, Eds., AAAI Press, 161--170."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1705"},{"key":"e_1_2_1_29_1","volume-title":"critical paths and abstractions: What's the difference anyway&quest","author":"Helmert Malte","unstructured":"Malte Helmert and Carmel Domshlak . 2009. Landmarks , critical paths and abstractions: What's the difference anyway&quest ; In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09). Alfonso Gerevini, Adele Howe, Amedeo Cesta, and Ioannis Refanidis, Eds., AAAI Press , 162--169. Malte Helmert and Carmel Domshlak. 2009. Landmarks, critical paths and abstractions: What's the difference anyway&quest; In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09). Alfonso Gerevini, Adele Howe, Amedeo Cesta, and Ioannis Refanidis, Eds., AAAI Press, 162--169."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS'07)","author":"Helmert Malte","year":"2007","unstructured":"Malte Helmert , Patrik Haslum , and J\u00f6rg Hoffmann . 2007 . Flexible abstraction heuristics for optimal sequential planning . In Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS'07) . Mark Boddy, Maria Fox, and Sylvie Thi\u00e9baux, Eds., AAAI Press, 176--183. Malte Helmert, Patrik Haslum, and J\u00f6rg Hoffmann. 2007. Flexible abstraction heuristics for optimal sequential planning. In Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS'07). Mark Boddy, Maria Fox, and Sylvie Thi\u00e9baux, Eds., AAAI Press, 176--183."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10)","author":"Helmert Malte","year":"2010","unstructured":"Malte Helmert and Hauke Lasinger . 2010 . The Scanalyzer domain: Greenhouse logistics as a planning problem , In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10) . Ronen brafman, H\u00e9ctor Geffner, J\u00f6rg Hoffmann, and Henry Kautz, Eds., AAAI Press, 234--237. Malte Helmert and Hauke Lasinger. 2010. The Scanalyzer domain: Greenhouse logistics as a planning problem, In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10). Ronen brafman, H\u00e9ctor Geffner, J\u00f6rg Hoffmann, and Henry Kautz, Eds., AAAI Press, 234--237."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.09.002"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 3rd Annual Symposium on Combinatorial Search (SoCS'10)","author":"Holte Robert C.","year":"2010","unstructured":"Robert C. Holte . 2010 . Common misconceptions concerning heuristic search . In Proceedings of the 3rd Annual Symposium on Combinatorial Search (SoCS'10) . Ariel Felner and Nathan Sturtevant, Eds., AAAI Press, 46--51. Robert C. Holte. 2010. Common misconceptions concerning heuristic search. In Proceedings of the 3rd Annual Symposium on Combinatorial Search (SoCS'10). Ariel Felner and Nathan Sturtevant, Eds., AAAI Press, 46--51."},{"key":"e_1_2_1_34_1","volume-title":"The SPIN Model Checker -- Primer and Reference Manual","author":"Holzmann Gerard J.","unstructured":"Gerard J. Holzmann . 2004. The SPIN Model Checker -- Primer and Reference Manual . Addison-Wesley . Gerard J. Holzmann. 2004. The SPIN Model Checker -- Primer and Reference Manual. Addison-Wesley."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1130\/0016-7606(1945)56[275:EDOSAT]2.0.CO;2"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08)","author":"Katz Michael","year":"2008","unstructured":"Michael Katz and Carmel Domshlak . 2008 . Optimal additive composition of abstraction-based admissible heuristics , In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08) . Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, Eds., AAAI Press 174--181. Michael Katz and Carmel Domshlak. 2008. Optimal additive composition of abstraction-based admissible heuristics, In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS'08). Jussi Rintanen, Bernhard Nebel, J. Christopher Beck, and Eric Hansen, Eds., AAAI Press 174--181."},{"key":"e_1_2_1_37_1","volume-title":"How to relax a bisimulation&quest","author":"Katz Michael","unstructured":"Michael Katz , J\u00f6rg Hoffmann , and Malte Helmert . 2012. How to relax a bisimulation&quest ; In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12). AAAI Press , 101--109. Michael Katz, J\u00f6rg Hoffmann, and Malte Helmert. 2012. How to relax a bisimulation&quest; In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12). AAAI Press, 101--109."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10)","author":"Koller Alexander","year":"2010","unstructured":"Alexander Koller and J\u00f6rg Hoffmann . 2010 . Waking up a sleeping rabbit: On natural-language sentence generation with FF . In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10) . Ronen Brafman, H\u00e9ctor Geffner, J\u00f6rg Hoffmann, and Henry Kautz, Eds., AAAI Press 238--241. Alexander Koller and J\u00f6rg Hoffmann. 2010. Waking up a sleeping rabbit: On natural-language sentence generation with FF. In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS'10). Ronen Brafman, H\u00e9ctor Geffner, J\u00f6rg Hoffmann, and Henry Kautz, Eds., AAAI Press 238--241."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.2010.00370.x"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 14th National Conference on Artificial Intelligence (AAAI'97)","author":"Korf Richard E.","year":"1997","unstructured":"Richard E. Korf . 1997 . Finding optimal solutions to Rubik's cube using pattern databases . In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI'97) . AAAI Press, 700--705. Richard E. Korf. 1997. Finding optimal solutions to Rubik's cube using pattern databases. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI'97). AAAI Press, 700--705."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00)","author":"Richard","unstructured":"Richard E. Korf and Weixiong Zhang. 2000. Divide-and-conquer frontier search applied to optimal sequence alignment . In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00) . Henry Kautz and Bruce Porter, Eds., AAAI Press, 910--916. Richard E. Korf and Weixiong Zhang. 2000. Divide-and-conquer frontier search applied to optimal sequence alignment. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00). Henry Kautz and Bruce Porter, Eds., AAAI Press, 910--916."},{"key":"e_1_2_1_42_1","volume-title":"Diagnosis of Active Systems","author":"Lamperti Gianfranco","unstructured":"Gianfranco Lamperti and Marina Zanella . 2003. Diagnosis of Active Systems . Kluwer Academic Publishers . Gianfranco Lamperti and Marina Zanella. 2003. Diagnosis of Active Systems. Kluwer Academic Publishers."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the AAAI Workshop on Intelligent Security (SecArt). 10--17","author":"Obes Jorge Lucangeli","year":"2010","unstructured":"Jorge Lucangeli Obes , Carlos Sarraute , and Gerardo Richarte . 2010 . Attack planning in the real world . In Proceedings of the AAAI Workshop on Intelligent Security (SecArt). 10--17 . Jorge Lucangeli Obes, Carlos Sarraute, and Gerardo Richarte. 2010. Attack planning in the real world. In Proceedings of the AAAI Workshop on Intelligent Security (SecArt). 10--17."},{"key":"e_1_2_1_45_1","series-title":"Lecture Notes in Computer Science","volume-title":"A Calculus of Communicating Systems","author":"Milner Robin","unstructured":"Robin Milner . 1980. A Calculus of Communicating Systems . Lecture Notes in Computer Science , vol. 92 , Springer-Verlag . Robin Milner. 1980. A Calculus of Communicating Systems. Lecture Notes in Computer Science, vol. 92, Springer-Verlag."},{"key":"e_1_2_1_46_1","volume-title":"Handbook of Theoretical Computer Science","author":"Milner Robin","unstructured":"Robin Milner . 1990. Operational and algebraic semantics of concurrent processes . In Handbook of Theoretical Computer Science , Volume B: Formal Models and Sematics, Jan van Leeuwen, Ed., Elsevier and MIT Press, 1201-- 1242 . Robin Milner. 1990. Operational and algebraic semantics of concurrent processes. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics, Jan van Leeuwen, Ed., Elsevier and MIT Press, 1201--1242."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622248.1622258"},{"key":"e_1_2_1_48_1","volume-title":"Simon","author":"Newell Allen","year":"1963","unstructured":"Allen Newell and Herbert A . Simon . 1963 . GPS : A program that simulates human thought. In Computers and Thought, E. A. Feigenbaum and J. Feldman, Eds., Oldenbourg , 279--293. Allen Newell and Herbert A. Simon. 1963. GPS: A program that simulates human thought. In Computers and Thought, E. A. Feigenbaum and J. Feldman, Eds., Oldenbourg, 279--293."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283696.2283732"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR'89)","author":"Pednault Edwin P. D.","year":"1989","unstructured":"Edwin P. D. Pednault . 1989 . ADL: Exploring the middle ground between STRIPS and the situation calculus . In Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR'89) . Ronald J. Brachman, Hector J. Levesque, and Raymond Reiter, Eds., Morgan Kaufmann, 324--332. Edwin P. D. Pednault. 1989. ADL: Exploring the middle ground between STRIPS and the situation calculus. In Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR'89). Ronald J. Brachman, Hector J. Levesque, and Raymond Reiter, Eds., Morgan Kaufmann, 324--332."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09)","author":"Richter Silvia","year":"2009","unstructured":"Silvia Richter and Malte Helmert . 2009 . Preferred operators and deferred evaluation in satisficing planning . In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09) . AAAI Press, 273--280. Silvia Richter and Malte Helmert. 2009. Preferred operators and deferred evaluation in satisficing planning. In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS'09). AAAI Press, 273--280."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016945.2016957"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.35374"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 10th International Conference on Applications and Theory of Petri Nets (APN'89)","volume":"483","author":"Valmari Antti","year":"1989","unstructured":"Antti Valmari . 1989 . Stubborn sets for reduced state space generation . In Proceedings of the 10th International Conference on Applications and Theory of Petri Nets (APN'89) Lecture Notes in Computer Science, Grzegorz Rozenberg, Ed. , vol. 483 , Springer-Verlag, 491--515. Antti Valmari. 1989. Stubborn sets for reduced state space generation. In Proceedings of the 10th International Conference on Applications and Theory of Petri Nets (APN'89) Lecture Notes in Computer Science, Grzegorz Rozenberg, Ed., vol. 483, Springer-Verlag, 491--515."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559951","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:25Z","timestamp":1750234225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559951"}},"subtitle":["A Method for Generating Lower Bounds in Factored State Spaces"],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2559951"],"URL":"https:\/\/doi.org\/10.1145\/2559951","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}