{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:41:32Z","timestamp":1743046892742,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031637414"},{"type":"electronic","value":"9783031637421"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-63742-1_16","type":"book-chapter","created":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T20:11:01Z","timestamp":1718655061000},"page":"219-236","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Agent Motion Planning as\u00a0Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and\u00a0More"],"prefix":"10.1007","author":[{"given":"Hayashi","family":"Ani","sequence":"first","affiliation":[]},{"given":"Josh","family":"Brunner","sequence":"additional","affiliation":[]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[]},{"given":"Jenny","family":"Diomidova","sequence":"additional","affiliation":[]},{"given":"Timothy","family":"Gomez","sequence":"additional","affiliation":[]},{"given":"Della","family":"Hendrickson","sequence":"additional","affiliation":[]},{"given":"Yael","family":"Kirkpatrick","sequence":"additional","affiliation":[]},{"given":"Jeffery","family":"Li","sequence":"additional","affiliation":[]},{"given":"Jayson","family":"Lynch","sequence":"additional","affiliation":[]},{"given":"Ritam","family":"Nag","sequence":"additional","affiliation":[]},{"given":"Frederick","family":"Stock","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,18]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L., et al.: Combinatorial optimization problems in self-assembly. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 23\u201332 (2002)","DOI":"10.1145\/509907.509913"},{"key":"16_CR2","unstructured":"Akitaya, H.A., et al.: Characterizing universal reconfigurability of modular pivoting robots. In: Proceedings of the 37th International Symposium on Computational Geometry (2021)"},{"key":"16_CR3","unstructured":"Alaniz, R.M., et al.: Complexity of reconfiguration in surface chemical reaction networks. In: Chen, H.-L., Evans, C.G. (Eds.) Proceedings of the 29th International Conference on DNA Computing and Molecular Programming (DNA 29), vol. 276. Leibniz International Proceedings in Informatics (LIPIcs), pp. 10:1\u201310:18, Dagstuhl, Germany (2023). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"key":"16_CR4","first-page":"929","volume":"28","author":"H Ani","year":"2020","unstructured":"Ani, H., et al.: PSPACE-completeness of pulling blocks to reach a goal. J. Inf. Process. 28, 929\u2013941 (2020)","journal-title":"J. Inf. Process."},{"key":"16_CR5","unstructured":"Ani, H., Chung, L., Demaine, E.D., Diomidova, J., Hendrickson, D., Lynch, J.: Pushing blocks via checkable gadgets: PSPACE-completeness of Push-1F and Block\/Box Dude. In: Proceedings of the 11th International Conference on Fun with Algorithms (FUN 2022) (2022)"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Berlekamp, E.R., Conway, J.H., Guy, R.K.: What is life? In: Winning Ways for Your Mathematical Plays, vol. 4. A K Peters, 2nd (edn.) (2004)","DOI":"10.1201\/9780429487309"},{"issue":"1","key":"16_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.25088\/ComplexSystems.15.1.1","volume":"15","author":"M Cook","year":"2004","unstructured":"Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1), 1\u201340 (2004)","journal-title":"Complex Syst."},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Defant, C., Kravitz, N.: Friends and strangers walking on graphs. Comb. Theory. 1 (2021)","DOI":"10.5070\/C61055363"},{"key":"16_CR9","unstructured":"Demaine, E.D., Grosof, I., Lynch, J., Rudoy, M.: Computational complexity of motion planning of a robot through simple gadgets. In: Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018) (2018)"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hearn, R.A., Hendrickson, D., Lynch, J.: PSPACE-completeness of reversible deterministic systems. In: Proceedings of the 9th Conference on Machines, Computations and Universality (MCU 2022), pp. 91\u2013108, Debrecen, Hungary, August\u2013September 2022","DOI":"10.1007\/978-3-031-13502-6_7"},{"key":"16_CR11","unstructured":"Demaine, E.D., Hendrickson, D.H., Lynch, J.: Toward a general complexity theory of motion planning: characterizing which gadgets make games hard. In: Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pp. 62:1\u201362:42 (2020)"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2018.04.031","volume":"732","author":"ED Demaine","year":"2018","unstructured":"Demaine, E.D., Rudoy, M.: A simple proof that the $$(n^2-1)$$-puzzle is hard. Theoret. Comput. Sci. 732, 80\u201384 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.tcs.2015.12.003","volume":"664","author":"A Dennunzio","year":"2017","unstructured":"Dennunzio, A., Formenti, E., Manzoni, L., Mauri, G., Porreca, A.E.: Computational complexity of finite asynchronous cellular automata. Theoret. Comput. Sci. 664, 131\u2013143 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Durand-Lose, J.: Representing reversible cellular automata with reversible block cellular automata. Discrete Mathematics & Theoretical Computer Science Proceedings, AA: Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), January 2001","DOI":"10.46298\/dmtcs.2297"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-642-40867-0_2","volume-title":"Cellular Automata and Discrete Complex Systems","author":"N Fat\u00e8s","year":"2013","unstructured":"Fat\u00e8s, N.: A guided tour of asynchronous cellular automata. In: Kari, J., Kutrib, M., Malcher, A. (eds.) AUTOMATA 2013. LNCS, vol. 8155, pp. 15\u201330. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40867-0_2"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-40273-9_13","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"R Fleischer","year":"2013","unstructured":"Fleischer, R., Yu, J.: A survey of the game \u201cLights Out!\u2019\u2019. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 176\u2013198. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40273-9_13"},{"issue":"1","key":"16_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1707801.1706301","volume":"45","author":"N Gershenfeld","year":"2010","unstructured":"Gershenfeld, N., et al.: Reconfigurable asynchronous logic automata. ACM SIGPLAN Not. 45(1), 1\u20136 (2010)","journal-title":"ACM SIGPLAN Not."},{"key":"16_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104764","volume":"281","author":"E Goles","year":"2021","unstructured":"Goles, E., Maldonado, D., Montealegre, P., R\u00edos-Wilson, M.: On the complexity of asynchronous freezing cellular automata. Inf. Comput. 281, 104764 (2021)","journal-title":"Inf. Comput."},{"key":"16_CR19","unstructured":"Goles, E., Ollinger, N., Theyssier, G.: Introducing freezing cellular automata. In: Proceedings of the 21st International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2015), vol. 24, pp. 65\u201373 (2015)"},{"key":"16_CR20","unstructured":"Group, M.H., et al.: Pushing blocks without fixed blocks via checkable gizmos: Push-1 is PSPACE-complete. Manuscript under submission (2024)"},{"key":"16_CR21","volume-title":"Cellular Automata: Theory and Experiment","author":"H Gutowitz","year":"1991","unstructured":"Gutowitz, H.: Cellular Automata: Theory and Experiment. MIT Press, Cambridge (1991)"},{"issue":"1","key":"16_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2004.11.021","volume":"334","author":"J Kari","year":"2005","unstructured":"Kari, J.: Theory of cellular automata: a survey. Theoret. Comput. Sci. 334(1), 3\u201333 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"16_CR23","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/0167-2789(86)90237-X","volume":"22","author":"CG Langton","year":"1986","unstructured":"Langton, C.G.: Studying artificial life with cellular automata. Physica D 22(1\u20133), 120\u2013149 (1986)","journal-title":"Physica D"},{"issue":"1","key":"16_CR24","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0167-2789(84)90252-5","volume":"10","author":"N Margolus","year":"1984","unstructured":"Margolus, N.: Physics-like models of computation. Physica D 10(1), 81\u201395 (1984)","journal-title":"Physica D"},{"key":"16_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2023.102668","volume":"155","author":"A Milojevi\u0107","year":"2024","unstructured":"Milojevi\u0107, A.: Connectivity of old and new models of friends-and-strangers graphs. Adv. Appl. Math. 155, 102668 (2024)","journal-title":"Adv. Appl. Math."},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/11786986_13","volume-title":"Automata, Languages and Programming","author":"T Neary","year":"2006","unstructured":"Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 132\u2013143. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11786986_13"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Ollinger, N., Theyssier, G.: Freezing, bounded-change and convergent cellular automata. Discr. Math. Theoret. Comput. Sci. 24(Automata, Logic and Semantics) (2022)","DOI":"10.46298\/dmtcs.5734"},{"key":"16_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-319-11295-4_8","volume-title":"DNA Computing and Molecular Programming","author":"L Qian","year":"2014","unstructured":"Qian, L., Winfree, E.: Parallel and scalable computation and spatial dynamics with DNA-based chemical reaction networks on a surface. In: Murata, S., Kobayashi, S. (eds.) DNA 2014. LNCS, vol. 8727, pp. 114\u2013131. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11295-4_8"},{"key":"16_CR29","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.: The $$(n^2-1)$$-puzzle and related relocation problems. J. Symb. Comput. 10, 111\u2013137 (1990)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"16_CR30","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jcss.1995.1009","volume":"50","author":"K Sutner","year":"1995","unstructured":"Sutner, K.: On the computational complexity of finite cellular automata. J. Comput. Syst. Sci. 50(1), 87\u201397 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6356","key":"16_CR31","doi-asserted-by":"publisher","first-page":"eaan6558","DOI":"10.1126\/science.aan6558","volume":"357","author":"AJ Thubagere","year":"2017","unstructured":"Thubagere, A.J., et al.: A cargo-sorting DNA robot. Science. 357(6356), eaan6558 (2017)","journal-title":"Science."},{"key":"16_CR32","doi-asserted-by":"crossref","unstructured":"Toffoli, T., Margolus, N.: Ii.12: The Margolus neighborhood. In: Cellular Automata Machines: A New Environment for Modeling, pp. 119\u2013138. MIT Press (1987)","DOI":"10.7551\/mitpress\/1763.001.0001"},{"issue":"1","key":"16_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3390\/a4010001","volume":"4","author":"T Tsukiji","year":"2011","unstructured":"Tsukiji, T., Hagiwara, T.: Recognizing the repeatable configurations of time-reversible generalized Langton\u2019s ant is PSPACE-hard. Algorithms 4(1), 1\u201315 (2011)","journal-title":"Algorithms"},{"key":"16_CR34","unstructured":"von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press (1966)"},{"key":"16_CR35","unstructured":"Winfree, E.: Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology (1998)"}],"container-title":["Lecture Notes in Computer Science","Unconventional Computation and Natural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63742-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T01:37:22Z","timestamp":1732239442000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63742-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031637414","9783031637421"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63742-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"18 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"UCNC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Unconventional Computation and Natural Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pohang","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","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":"17 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"uc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/ucnc-2024","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}