{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T17:05:50Z","timestamp":1780074350696,"version":"3.54.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,4]],"date-time":"2020-09-04T00:00:00Z","timestamp":1599177600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,4]],"date-time":"2020-09-04T00:00:00Z","timestamp":1599177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE407\/17-2"],"award-info":[{"award-number":["FE407\/17-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Projekt DEAL"},{"DOI":"10.13039\/501100004871","name":"Technische Universit\u00e4t Braunschweig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We contribute results for a set of fundamental problems in the context of programmable matter by presenting algorithmic methods for evaluating and manipulating a collective of particles by a finite automaton that can neither store significant amounts of data, nor perform complex computations, and is limited to a handful of possible physical operations. We provide a toolbox for carrying out fundamental tasks on a given arrangement of particles, using the arrangement itself as a storage device, similar to a higher-dimensional Turing machine with geometric properties. Specific results include time- and space-efficient procedures for bounding, counting, copying, reflecting, rotating or scaling a complex given shape.<\/jats:p>","DOI":"10.1007\/s00453-020-00761-z","type":"journal-article","created":{"date-parts":[[2020,9,4]],"date-time":"2020-09-04T09:02:43Z","timestamp":1599210163000},"page":"387-412","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Gmyr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sabrina","family":"Hugo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phillip","family":"Keldenich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Scheffer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arne","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,9,4]]},"reference":[{"key":"761_CR1","unstructured":"Abdel-Rahman, A., Becker, A.T., Biediger, D.E., Cheung, K.C., Fekete, S.P., Gershenfeld, N.A., Hugo, S., Jenett, B., Keldenich, P., Niehs, E., Rieck, C., Schmidt, A., Scheffer, C., Yannuzzi, M.: Space ants: constructing and reconfiguring large-scale structures with finite automata. In: Symposium on Computations Geometry (SoCG), pp. 73:1\u201373:7 (2020). Video at https:\/\/www.ibr.cs.tu-bs.de\/users\/fekete\/Videos\/SoCG\/2020\/Space_final.mp4"},{"issue":"1","key":"761_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s11047-017-9666-6","volume":"18","author":"AT Becker","year":"2019","unstructured":"Becker, A.T., Demaine, E.D., Fekete, S.P., Lonsford, J., Morris-Wright, R.: Particle computation: complexity, algorithms, and logic. Nat. Comput. 18(1), 181\u2013201 (2019)","journal-title":"Nat. Comput."},{"key":"761_CR3","doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Symposium on Foundations of Computer Science (FOCS), pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"761_CR4","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/061","volume-title":"The Game of Cops and Robbers on Graphs","author":"A Bonato","year":"2011","unstructured":"Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. AMS, Providence (2011)"},{"key":"761_CR5","first-page":"54","volume":"109","author":"S Das","year":"2013","unstructured":"Das, S.: Mobile agents in distributed computing: network exploration. Bull. Eur. Assoc. Theor. Comput. Sci. 109, 54\u201369 (2013)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"761_CR6","doi-asserted-by":"crossref","unstructured":"Daymude, J.J., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Improved leader election for self-organizing programmable matter. In: International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), pp. 127\u2013140 (2017)","DOI":"10.1007\/978-3-319-72751-6_10"},{"issue":"1","key":"761_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0925-7721(02)00170-0","volume":"26","author":"E Demaine","year":"2003","unstructured":"Demaine, E., Demaine, M., Hoffmann, M., O\u2019Rourke, J.: Pushing blocks is hard. Comput. Geom. 26(1), 21\u201336 (2003)","journal-title":"Comput. Geom."},{"key":"761_CR8","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.tcs.2016.11.020","volume":"671","author":"ED Demaine","year":"2017","unstructured":"Demaine, E.D., Fekete, S.P., Scheffer, C., Schmidt, A.: New geometric algorithms for fully connected staged self-assembly. Theoret. Comput. Sci. 671, 4\u201318 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"761_CR9","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: Amoebot\u2014a new model for programmable matter. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 220\u2013222 (2014)","DOI":"10.1145\/2612669.2612712"},{"key":"761_CR10","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Porter, A., Richa, A.W., Scheideler, C., Strothmann, T.: On the runtime of universal coating for programmable matter. In: International Conference on DNA Computing and Molecular Programming (DNA), pp. 148\u2013164 (2016)","DOI":"10.1007\/978-3-319-43994-5_10"},{"key":"761_CR11","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: An algorithmic framework for shape formation problems in self-organizing particle systems. In: International Conference on Nanoscale Computing and Communication (NANOCOM), pp. 21 (2015)","DOI":"10.1145\/2800795.2800829"},{"key":"761_CR12","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal shape formation for programmable matter. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 289\u2013299 (2016)","DOI":"10.1145\/2935764.2935784"},{"key":"761_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2016.02.039","volume":"671","author":"Z Derakhshandeh","year":"2017","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal coating for programmable matter. Theoret. Comput. Sci. 671, 56\u201368 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"761_CR14","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Strothmann, T., Bazzi, R., Richa, A.W., Scheideler, C.: Leader election and shape formation with self-organizing programmable matter. In: International Conference on DNA Computing and Molecular Programming (DNA), pp. 117\u2013132 (2015)","DOI":"10.1007\/978-3-319-21999-8_8"},{"key":"761_CR15","first-page":"1","volume":"33","author":"GA Di Luna","year":"2019","unstructured":"Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. Distrib. Comput. 33, 1\u201333 (2019)","journal-title":"Distrib. Comput."},{"key":"761_CR16","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Gmyr, R., Hugo, S., Keldenich, P., Scheffer, C., Schmidt, A.: CADbots: algorithmic aspects of manipulating porgrammable matter with finite automata. In: Algorithmic Foundations of Robotics XIII (WAFR 2018), Springer Proceedings in Advanced Robotics, pp. 725\u2013743 (2020)","DOI":"10.1007\/978-3-030-44051-0_42"},{"issue":"3","key":"761_CR17","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","volume":"399","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theoret. Comput. Sci. 399(3), 236\u2013245 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"761_CR18","unstructured":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C.: Shape recognition by a finite automaton robot. In: International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 52:1\u201352:15 (2018)"},{"key":"761_CR19","doi-asserted-by":"crossref","unstructured":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., Strothmann, T.: Forming tile shapes with simple robots. In: International Conference on DNA Computing and Molecular Programming (DNA), pp. 122\u2013138 (2018)","DOI":"10.1007\/978-3-030-00030-1_8"},{"issue":"4","key":"761_CR20","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10514-015-9421-8","volume":"38","author":"F Hurtado","year":"2015","unstructured":"Hurtado, F., Molina, E., Ramaswami, S., Sacrist\u00e1n, V.: Distributed reconfiguraiton of 2D lattice-based modular robotic systems. Auton. Robots 38(4), 383\u2013413 (2015)","journal-title":"Auton. Robots"},{"issue":"7295","key":"761_CR21","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1038\/nature09012","volume":"465","author":"K Lund","year":"2010","unstructured":"Lund, K., Manzo, A., Dabby, N., Michelotti, N., Johnson-Buck, A., Nangreave, J., Taylor, S., Pei, R., Stojanovic, M., Walter, N., Winfree, E.: Molecular robots guided by prescriptive landscapes. Nature 465(7295), 206\u2013210 (2010)","journal-title":"Nature"},{"key":"761_CR22","first-page":"93","volume":"108","author":"E Markou","year":"2012","unstructured":"Markou, E.: Identifying hostile nodes in networks using mobile agents. Bull. Eur. Assoc. Theor. Comput. Sci. 108, 93\u2013129 (2012)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"3","key":"761_CR23","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00446-015-0257-4","volume":"29","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. Distrib. Comput. 29(3), 207\u2013237 (2016)","journal-title":"Distrib. Comput."},{"key":"761_CR24","doi-asserted-by":"crossref","unstructured":"Niehs, E., Schmidt, A., Scheffer, C., Biediger, D.E., Yannuzzi, M., Jenett, B., Abdel-Rahman, A., Cheung, K.C., Becker, A.T., Fekete, S.P.: Recognition and reconfiguration of lattice-based cellular structures by simple robots. In: International Conference on Robotics and Automation (ICRA) (2020) (to appear)","DOI":"10.1109\/ICRA40945.2020.9196700"},{"issue":"5923","key":"761_CR25","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1126\/science.1170336","volume":"324","author":"T Omabegho","year":"2009","unstructured":"Omabegho, T., Sha, R., Seeman, N.: A bipedal DNA Brownian motor with coordinated legs. Science 324(5923), 67\u201371 (2009)","journal-title":"Science"},{"issue":"2","key":"761_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s11047-013-9379-4","volume":"13","author":"MJ Patitz","year":"2014","unstructured":"Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Nat. Comput. 13(2), 195\u2013224 (2014)","journal-title":"Nat. Comput."},{"issue":"3","key":"761_CR27","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/net.21453","volume":"59","author":"A Pelc","year":"2012","unstructured":"Pelc, A.: Deterministic rendezvous in networks: a comprehensive survey. Networks 59(3), 331\u2013347 (2012)","journal-title":"Networks"},{"key":"761_CR28","doi-asserted-by":"publisher","first-page":"1428","DOI":"10.1016\/j.tcs.2008.12.003","volume":"410","author":"JH Reif","year":"2009","unstructured":"Reif, J.H., Sahu, S.: Autonomous programmable DNA nanorobotic devices using dnazymes. Theoret. Comput. Sci. 410, 1428\u20131439 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"761_CR29","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0146-664X(74)90017-3","volume":"3","author":"AN Shah","year":"1974","unstructured":"Shah, A.N.: Pebble automata on arrays. Comput. Graph. Image Process. 3(3), 236\u2013246 (1974)","journal-title":"Comput. Graph. Image Process."},{"key":"761_CR30","first-page":"4903","volume":"126","author":"J Shin","year":"2004","unstructured":"Shin, J., Pierce, N.: A synthetic DNA walker for molecular transport. J. Am. Chem. Soc. 126, 4903\u20134911 (2004)","journal-title":"J. Am. Chem. Soc."},{"issue":"3\u20134","key":"761_CR31","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1177\/0278364907085562","volume":"27","author":"Y Terada","year":"2008","unstructured":"Terada, Y., Murata, S.: Automatic modular assembly system and its distributed control. Int. J. Robot. Res. 27(3\u20134), 445\u2013462 (2008)","journal-title":"Int. J. Robot. Res."},{"issue":"6356","key":"761_CR32","doi-asserted-by":"publisher","first-page":"eaan6558","DOI":"10.1126\/science.aan6558","volume":"357","author":"A Thubagere","year":"2017","unstructured":"Thubagere, A., Li, W., Johnson, R., Chen, Z., Doroudi, S., Lee, Y., Izatt, G., Wittman, S., Srinivas, N., Woods, D., Winfree, E., Qian, L.: A cargo-sorting DNA robot. Science 357(6356), eaan6558 (2017)","journal-title":"Science"},{"issue":"48","key":"761_CR33","doi-asserted-by":"publisher","first-page":"4322","DOI":"10.1002\/anie.201107855","volume":"51","author":"Z Wang","year":"2012","unstructured":"Wang, Z., Elbaz, J., Willner, I.: A dynamically programmed DNA transporter. Angew. Chem. Int. Ed. 51(48), 4322\u20134326 (2012)","journal-title":"Angew. Chem. Int. Ed."},{"issue":"3","key":"761_CR34","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1038\/nnano.2011.253","volume":"7","author":"S Wickham","year":"2012","unstructured":"Wickham, S., Bath, J., Katsuda, Y., Endo, M., Hidaka, K., Sugiyama, H., Turberfield, A.: A DNA-based molecular motor that can navigate a network of tracks. Nat. Nanotechnol. 7(3), 169\u2013173 (2012)","journal-title":"Nat. Nanotechnol."},{"key":"761_CR35","doi-asserted-by":"crossref","unstructured":"Woods, D., Chen, H., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Innovations in Theoretical Computer Science (ITCS), pp. 353\u2013354 (2013)","DOI":"10.1145\/2422436.2422476"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00761-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00761-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00761-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,4]],"date-time":"2021-09-04T01:52:05Z","timestamp":1630720325000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00761-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,4]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["761"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00761-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,4]]},"assertion":[{"value":"9 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}