{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T02:46:31Z","timestamp":1777689991989,"version":"3.51.4"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,8,23]],"date-time":"2017-08-23T00:00:00Z","timestamp":1503446400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000836","name":"University of Liverpool","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000836","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00446-017-0309-z","type":"journal-article","created":{"date-parts":[[2017,8,23]],"date-time":"2017-08-23T06:20:19Z","timestamp":1503469219000},"page":"343-365","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Terminating distributed construction of shapes and patterns in a fair solution of automata"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6234-3960","authenticated-orcid":false,"given":"Othon","family":"Michail","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,23]]},"reference":[{"key":"309_CR1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"key":"309_CR2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s00446-008-0067-z","volume":"21","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distrib. Comput. 21, 183\u2013199 (2008)","journal-title":"Distrib. Comput."},{"key":"309_CR3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","volume":"20","author":"D Angluin","year":"2007","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20, 279\u2013304 (2007)","journal-title":"Distrib. Comput."},{"key":"309_CR4","doi-asserted-by":"crossref","unstructured":"Abel, Z., Benbernou, N., Damian, M., Demaine, E.D., Demaine, M.L., Flatland, R., Kominers, S.D., Schweller, R.: Shape replication through self-assembly and RNase enzymes. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1045\u20131064. SIAM (2010)","DOI":"10.1137\/1.9781611973075.85"},{"key":"309_CR5","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1016\/j.comgeo.2013.03.004","volume":"46","author":"G Aloupis","year":"2013","unstructured":"Aloupis, G., Benbernou, N., Damian, M., Demaine, E.D., Flatland, R., Iacono, J., Wuhrer, S.: Efficient reconfiguration of lattice-based modular robots. Comput. Geom. 46, 917\u2013928 (2013)","journal-title":"Comput. Geom."},{"key":"309_CR6","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"LM Adleman","year":"1994","unstructured":"Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266, 1021\u20131024 (1994)","journal-title":"Science"},{"key":"309_CR7","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82\u201393. ACM (1980)","DOI":"10.1145\/800141.804655"},{"key":"309_CR8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-89707-1_5","volume-title":"Middleware for Network Eccentric and Mobile Applications","author":"J Aspnes","year":"2009","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Garbinato, B., Miranda, H., Rodrigues, L. (eds.) Middleware for Network Eccentric and Mobile Applications, pp. 97\u2013120. Springer, Berlin (2009)"},{"key":"309_CR9","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations, and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, vol. 19. Wiley, New York (2004)"},{"key":"309_CR10","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Burman, J., Clement, J., Kutten, S.: On utilizing speed in networks of mobile agents. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 305\u2013314. ACM (2010)","DOI":"10.1145\/1835698.1835775"},{"key":"309_CR11","doi-asserted-by":"crossref","unstructured":"Chalk, C., Demaine, E.D., Demaine, M.L., Martinez, E., Schweller, R., Vega, L., Wylie, T.: Universal shape replicators via self-assembly with attractive and repulsive forces. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 225\u2013238. SIAM (2017)","DOI":"10.1137\/1.9781611974782.15"},{"key":"309_CR12","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s11047-013-9393-6","volume":"13","author":"H-L Chen","year":"2014","unstructured":"Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 13, 517\u2013534 (2014)","journal-title":"Nat. Comput."},{"key":"309_CR13","doi-asserted-by":"crossref","first-page":"6469","DOI":"10.1016\/j.tcs.2011.07.001","volume":"412","author":"I Chatzigiannakis","year":"2011","unstructured":"Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: Passively mobile communicating machines that use restricted space. Theor. Comput. Sci. 412, 6469\u20136483 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"309_CR14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s11047-014-9432-y","volume":"14","author":"M Chen","year":"2015","unstructured":"Chen, M., Xin, D., Woods, D.: Parallel computation using active self-assembly. Nat. Comput. 14, 225\u2013250 (2015)","journal-title":"Nat. Comput."},{"key":"309_CR15","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: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 220\u2013222. ACM (2014)","DOI":"10.1145\/2612669.2612712"},{"key":"309_CR16","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00446-014-0220-9","volume":"28","author":"S Das","year":"2015","unstructured":"Das, S., Flocchini, P., Santoro, N., Yamashita, M.: Forming sequences of geometric patterns with oblivious mobile robots. Distrib. Comput. 28, 131\u2013145 (2015)","journal-title":"Distrib. Comput."},{"key":"309_CR17","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal shape formation for programmable matter. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 289\u2013299. ACM (2016)","DOI":"10.1145\/2935764.2935784"},{"key":"309_CR18","unstructured":"Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C.: Ameba-inspired self-organizing particle systems. arXiv preprint arXiv:1307.4259 (2013)"},{"key":"309_CR19","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. arXiv preprint arXiv:1705.03538 (2017)","DOI":"10.1145\/3154273.3154309"},{"key":"309_CR20","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/2380656.2380675","volume":"55","author":"D Doty","year":"2012","unstructured":"Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55, 78\u201388 (2012)","journal-title":"Commun. ACM"},{"key":"309_CR21","doi-asserted-by":"crossref","unstructured":"Doty, D.: Timing in chemical reaction networks. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 772\u2013784 (2014)","DOI":"10.1137\/1.9781611973402.57"},{"key":"309_CR22","first-page":"311","volume":"8","author":"P Ehrenfest","year":"1907","unstructured":"Ehrenfest, P., Ehrenfest-Afanassjewa, T.: \u00dcber zwei bekannte einw\u00e4nde gegen das boltzmannsche h-theorem. Phys. Zeit. 8, 311\u2013314 (1907)","journal-title":"Phys. Zeit."},{"key":"309_CR23","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, New York (1968). (Revised Printing)","edition":"3"},{"key":"309_CR24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1109\/MC.2005.198","volume":"38","author":"SC Goldstein","year":"2005","unstructured":"Goldstein, S.C., Campbell, J.D., Mowry, T.C.: Programmable matter. Computer 38, 99\u2013101 (2005)","journal-title":"Computer"},{"key":"309_CR25","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Ruppert, E.: Names trump malice: tiny mobile agents can tolerate byzantine failures. In: 36th International Colloquium on Automata, Languages and Programming (ICALP), Volume 5556 of LNCS, pp. 484\u2013495. Springer (2009)","DOI":"10.1007\/978-3-642-02930-1_40"},{"key":"309_CR26","doi-asserted-by":"crossref","unstructured":"Hendricks, J., Patitz, M.J., Rogers, T.A.: Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles. In: International Conference on Unconventional Computation and Natural Computation, pp. 202\u2013214. Springer (2015)","DOI":"10.1007\/978-3-319-21819-9_15"},{"issue":"7","key":"309_CR27","doi-asserted-by":"crossref","first-page":"369","DOI":"10.2307\/2304386","volume":"54","author":"M Kac","year":"1947","unstructured":"Kac, M.: Random walk and the theory of brownian motion. Am. Math. Mon. 54(7), 369\u2013391 (1947)","journal-title":"Am. Math. Mon."},{"key":"309_CR28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/s11047-014-9431-z","volume":"14","author":"A Keenan","year":"2015","unstructured":"Keenan, A., Schweller, R., Zhong, X.: Exponential replication of patterns in the signal tile assembly model. Nat. Comput. 14, 265\u2013278 (2015)","journal-title":"Nat. Comput."},{"key":"309_CR29","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms, 1st edn. Morgan Kaufmann Inc, San Francisco (1996)","edition":"1"},{"key":"309_CR30","doi-asserted-by":"crossref","first-page":"2434","DOI":"10.1016\/j.tcs.2011.02.003","volume":"412","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412, 2434\u20132450 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"309_CR31","volume-title":"Synthesis Lectures on Distributed Computing Theory","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New models for population protocols. In: Lynch, N.A. (ed.) Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2011)"},{"key":"309_CR32","doi-asserted-by":"crossref","unstructured":"Michail, O.: Terminating distributed construction of shapes and patterns in a fair solution of automata. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 37\u201346. ACM (2015)","DOI":"10.1145\/2767386.2767402"},{"issue":"3","key":"309_CR33","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00446-015-0257-4v","volume":"29","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. Dist. Comput. 29(3), 207\u2013237 (2016). doi: 10.1007\/s00446-015-0257-4v","journal-title":"Dist. Comput."},{"key":"309_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jpdc.2015.02.005","volume":"81","author":"O Michail","year":"2015","unstructured":"Michail, O., Spirakis, P.G.: Terminating population protocols via some minimal global knowledge assumptions. J. Parallel Distrib. Comput. (JPDC) 81, 1\u201310 (2015)","journal-title":"J. Parallel Distrib. Comput. (JPDC)"},{"key":"309_CR35","unstructured":"Michail, O., Spirakis, P.G.: Elements of the theory of dynamic networks. Commun. ACM (2017). https:\/\/livrepository.liverpool.ac.uk\/3006836\/ (To appear)"},{"key":"309_CR36","unstructured":"Michail, O., Skretas, G., Spirakis, P.G.: On the transformation capability of feasible mechanisms for programmable matter. In: Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP), pp. 136:1\u2013136:15 (2017)"},{"key":"309_CR37","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1142\/S0129054114400061","volume":"25","author":"JE Padilla","year":"2014","unstructured":"Padilla, J.E., Patitz, M.J., Schweller, R.T., Seeman, N.C., Summers, S.M., Zhong, X.: Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. Int. J. Found. Comput. Sci. 25, 459\u2013488 (2014)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"309_CR38","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1126\/science.1254295","volume":"345","author":"M Rubenstein","year":"2014","unstructured":"Rubenstein, M., Cornejo, A., Nagpal, R.: Programmable self-assembly in a thousand-robot swarm. Science 345, 795\u2013799 (2014)","journal-title":"Science"},{"key":"309_CR39","doi-asserted-by":"crossref","unstructured":"Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 459\u2013468 (2000)","DOI":"10.1145\/335305.335358"},{"key":"309_CR40","volume-title":"Cellular Automata: A Discrete View of the World","author":"JL Schiff","year":"2011","unstructured":"Schiff, J.L.: Cellular Automata: A Discrete View of the World, vol. 45. Wiley, New York (2011)"},{"key":"309_CR41","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s11047-008-9067-y","volume":"7","author":"D Soloveichik","year":"2008","unstructured":"Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615\u2013633 (2008)","journal-title":"Nat. Comput."},{"key":"309_CR42","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","volume":"28","author":"I Suzuki","year":"1999","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."},{"key":"309_CR43","unstructured":"Woods, D., Chen, H.-L., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 353\u2013354. ACM (2013). Full version: arXiv preprint arXiv:1301.2626"},{"key":"309_CR44","unstructured":"Winfree, E.: Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology, June (1998)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0309-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0309-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0309-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T16:55:15Z","timestamp":1659372915000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0309-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,23]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["309"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0309-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,23]]}}}