{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:44:41Z","timestamp":1725525881595},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642004308"},{"type":"electronic","value":"9783642004315"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00431-5_4","type":"book-chapter","created":{"date-parts":[[2009,2,24]],"date-time":"2009-02-24T01:14:35Z","timestamp":1235438075000},"page":"49-64","source":"Crossref","is-referenced-by-count":1,"title":["Scaling Search with Pattern Databases"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahid","family":"Jabbar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Kissmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-540-73580-9_5","volume-title":"Abstraction, Reformulation, and Approximation","author":"K. Anderson","year":"2007","unstructured":"Anderson, K., Holte, R., Schaeffer, J.: Partial pattern databases. In: Miguel, I., Ruml, W. (eds.) SARA 2007. LNCS, vol.\u00a04612, pp. 20\u201334. Springer, Heidelberg (2007)"},{"key":"4_CR2","unstructured":"Ball, M., Holte, R.: The compression power of symbolic pattern databases. In: International Conference on Automated Planning and Scheduling (ICAPS), pp. 2\u201311 (2008)"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1145\/136035.136043","volume":"24","author":"R.E. Bryant","year":"1992","unstructured":"Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys\u00a024(3), 142\u2013170 (1992)","journal-title":"ACM Computing Surveys"},{"issue":"5","key":"4_CR4","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1145\/186025.186051","volume":"16","author":"E. Clarke","year":"1994","unstructured":"Clarke, E., Grumberg, O., Long, D.: Model checking and abstraction. ACM Transactions on Programming Language Systems\u00a016(5), 1512\u20131542 (1994)","journal-title":"ACM Transactions on Programming Language Systems"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Principles of Programming Languages (POPL), pp. 238\u2013252 (1977)","DOI":"10.1145\/512950.512973"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1111\/0824-7935.00065","volume":"14","author":"J.C. Culberson","year":"1998","unstructured":"Culberson, J.C., Schaeffer, J.: Pattern databases. Computational Intelligence\u00a014(4), 318\u2013334 (1998)","journal-title":"Computational Intelligence"},{"key":"4_CR7","unstructured":"Edelkamp, S.: Symbolic pattern databases in heuristic search planning. In: Artificial Intelligence Planning and Scheduling (AIPS), pp. 274\u2013293 (2002)"},{"key":"4_CR8","unstructured":"Edelkamp, S.: External symbolic heuristic search with pattern databases. In: International Conference on Automated Planning and Scheduling (ICAPS), pp. 51\u201360 (2005)"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Edelkamp, S.: Optimizing admissible planning pattern database heuristics with genetic programming. In: Workshop on Model Checking and Artificial Intelligence (MoChArt), pp. 35\u201350 (2007)","DOI":"10.1007\/978-3-540-74128-2_3"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","first-page":"233","volume-title":"KI 2004: Advances in Artificial Intelligence","author":"S. Edelkamp","year":"2004","unstructured":"Edelkamp, S., Jabbar, S., Schr\u00f6dl, S.: External A*. In: Biundo, S., Fr\u00fchwirth, T., Palm, G. (eds.) KI 2004. LNCS (LNAI), vol.\u00a03238, pp. 233\u2013250. Springer, Heidelberg (2004)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Kissmann, P.: Limits and possibilities of BDDs for state space search. In: National Conference on Artificial Intelligence (AAAI), pp. 1452\u20131453 (2008)","DOI":"10.1007\/978-3-540-85845-4_6"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-540-85845-4_24","volume-title":"KI 2008: Advances in Artificial Intelligence","author":"S. Edelkamp","year":"2008","unstructured":"Edelkamp, S., Kissmann, P.: Partial symbolic pattern databases for optimal sequential planning. In: Dengel, A.R., Berns, K., Breuel, T.M., Bomarius, F., Roth-Berghofer, T.R. (eds.) KI 2008. LNCS, vol.\u00a05243, pp. 193\u2013200. Springer, Heidelberg (2008)"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s10009-002-0104-3","volume":"5","author":"S. Edelkamp","year":"2004","unstructured":"Edelkamp, S., Leue, S., Lluch-Lafuente, A.: Directed explicit-state model checking in the validation of communication protocols. International Journal on Software Tools for Technology Transfer\u00a05, 247\u2013267 (2004)","journal-title":"International Journal on Software Tools for Technology Transfer"},{"key":"4_CR14","unstructured":"Edelkamp, S., Lluch-Lafuente, A.: Abstraction in directed model checking. In: ICAPS-Workshop on Connecting Planning Theory with Practice (2004)"},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1613\/jair.1480","volume":"22","author":"A. Felner","year":"2004","unstructured":"Felner, A., Korf, R., Hanan, S.: Additive pattern databases. Journal of Artificial Intelligence Research\u00a022, 279\u2013318 (2004)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-540-73580-9_14","volume-title":"Abstraction, Reformulation, and Approximation","author":"A. Felner","year":"2007","unstructured":"Felner, A., Ofek, N.: Combining perimeter search and pattern database abstractions. In: Miguel, I., Ruml, W. (eds.) SARA 2007. LNCS, vol.\u00a04612, pp. 155\u2013168. Springer, Heidelberg (2007)"},{"key":"#cr-split#-4_CR17.1","unstructured":"Haslum, P.: Domain-independent construction of pattern database heuristics for cost-optimal planning (2007);"},{"key":"#cr-split#-4_CR17.2","unstructured":"Personal communications"},{"key":"4_CR18","unstructured":"Hung, N.N.W.: Exploiting symmetry for formal verification. Master\u2019s thesis, Faculty of the Graduate School, University of Texas at Austin (1997)"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-540-30579-8_21","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"S. Jabbar","year":"2005","unstructured":"Jabbar, S., Edelkamp, S.: I\/O efficient directed model checking. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol.\u00a03385, pp. 313\u2013329. Springer, Heidelberg (2005)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/11609773_16","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"S. Jabbar","year":"2005","unstructured":"Jabbar, S., Edelkamp, S.: Parallel external directed model checking with linear I\/O. In: Emerson, E.A., Namjoshi, K.S. (eds.) VMCAI 2006. LNCS, vol.\u00a03855, pp. 237\u2013251. Springer, Heidelberg (2005)"},{"key":"4_CR21","unstructured":"Jensen, R.M., Bryant, R.E., Veloso, M.M.: SetA*: An efficient BDD-based heuristic search algorithm. In: National Conference on Artificial Intelligence (AAAI), pp. 668\u2013673 (2002)"},{"key":"4_CR22","unstructured":"Katz, M., Domshlak, C.: Optimal additive composition of abstraction-based admissible heuristics. In: International Conference on Automated Planning and Scheduling (ICAPS), pp. 174\u2013181 (2008)"},{"key":"4_CR23","unstructured":"Katz, M., Domshlak, C.: Structural pattern heuristics via fork decomposition. In: International Conference on Automated Planning and Scheduling (ICAPS), pp. 182\u2013189 (2008)"},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"R.E. Korf","year":"1985","unstructured":"Korf, R.E.: Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence Journal\u00a027(1), 97\u2013109 (1985)","journal-title":"Artificial Intelligence Journal"},{"key":"4_CR25","unstructured":"Korf, R.E.: Finding optimal solutions to Rubik\u2019s Cube using pattern databases. In: National Conference on Artificial Intelligence (AAAI), pp. 700\u2013705 (1997)"},{"key":"4_CR26","unstructured":"Korf, R.E.: Breadth-first frontier search with delayed duplicate detection. In: Workshop on Model Checking and Artificial Intelligence (MoChArt), pp. 87\u201392 (2003)"},{"key":"4_CR27","first-page":"13","volume-title":"Chips Challenging Champions: Games, Computers and Artificial Intelligence","author":"R.E. Korf","year":"2002","unstructured":"Korf, R.E., Felner, A.: Disjoint Pattern Database Heuristics. In: Chips Challenging Champions: Games, Computers and Artificial Intelligence, pp. 13\u201326. Elsevier, Amsterdam (2002)"},{"key":"4_CR28","unstructured":"Korf, R.E., Felner, A.: Recent progress in heuristic search: A case study of the four-peg towers of hanoi problem. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 2324\u20132329 (2007)"},{"issue":"4","key":"4_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1330311.1330319","volume":"51","author":"D. Kunkle","year":"2008","unstructured":"Kunkle, D., Cooperman, G.: Solving Rubik\u2019s Cube: disk is the new RAM. Communications of the ACM\u00a051(4), 31\u201333 (2008)","journal-title":"Communications of the ACM"},{"key":"4_CR30","volume-title":"Computer-Aided Verification of Coordinating Processes: The Automata-Theoretic Approach","author":"R. Kurshan","year":"1994","unstructured":"Kurshan, R.: Computer-Aided Verification of Coordinating Processes: The Automata-Theoretic Approach. Princeton University Press, Princeton (1994)"},{"key":"4_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3190-6","volume-title":"Symbolic Model Checking","author":"K. McMillan","year":"1993","unstructured":"McMillan, K.: Symbolic Model Checking. Kluwer Academic Publishers, Dordrecht (1993)"},{"key":"4_CR32","first-page":"52","volume-title":"Design Automation Conference (DAC)","author":"S. Minato","year":"1990","unstructured":"Minato, S., Ishiura, N., Yajima, S.: Shared binary decision diagram with attributed edges for efficient boolean function manipulation. In: Design Automation Conference (DAC), pp. 52\u201357. IEEE Computer Society Press, Los Alamitos (1990)"},{"key":"4_CR33","unstructured":"Munagala, K., Ranade, A.: I\/O-complexity of graph algorithms. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 687\u2013694 (1999)"},{"key":"4_CR34","volume-title":"Heuristics: Intelligent Search Strategies for Computer Problem Solving","author":"J. Pearl","year":"1984","unstructured":"Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading (1984)"},{"key":"4_CR35","unstructured":"Qian, K.: Formal Verification Using Heuristic Search and Abstraction Techniques. PhD thesis, Computer Science & Engineering, The University of New South Wales (2006)"},{"key":"4_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-540-24730-2_37","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"K. Qian","year":"2004","unstructured":"Qian, K., Nymeyer, A.: Guided invariant model checking based on abstraction and symbolic pattern databases. In: Jensen, K., Podelski, A. (eds.) TACAS 2004. LNCS, vol.\u00a02988, pp. 497\u2013511. Springer, Heidelberg (2004)"},{"issue":"2","key":"4_CR37","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D. Ratner","year":"1990","unstructured":"Ratner, D., Warmuth, M.K.: The (n 2\u2009\u2212\u20091)-puzzle and related relocation problems. Journal of Symbolic Computation\u00a010(2), 111\u2013137 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"4_CR38","unstructured":"Zhou, R., Hansen, E.: External-memory pattern databases using structured duplicate detection. In: National Conference on Artificial Intelligence (AAAI), pp. 1398\u20131405 (2005)"},{"issue":"4\u20135","key":"4_CR39","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.artint.2005.12.002","volume":"170","author":"R. Zhou","year":"2006","unstructured":"Zhou, R., Hansen, E.A.: Breadth-first heuristic search. Artificial Intelligence Journal\u00a0170(4\u20135), 385\u2013408 (2006)","journal-title":"Artificial Intelligence Journal"}],"container-title":["Lecture Notes in Computer Science","Model Checking and Artificial Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00431-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T02:33:43Z","timestamp":1558146823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00431-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642004308","9783642004315"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00431-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}