{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:44:26Z","timestamp":1649180666018},"reference-count":4,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>In cellular automata with multiple speeds for each cell i<\/jats:italic> there is a positive integer $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that this cell updates its state still periodically but only at times which are a multiple of $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Additionally there is a finite upper bound on all $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Manzoni and Umeo have described an algorithm for these (one-dimensional) cellular automata which solves the Firing Squad Synchronization Problem. This algorithm needs linear time (in the number of cells to be synchronized) but for many problem instances it is slower than the optimum time by some positive constant factor. In the present paper we derive lower bounds on possible synchronization times and describe an algorithm which is never slower and in some cases faster than the one by Manzoni and Umeo and which is close to a lower bound (up to a constant summand) in more cases.<\/jats:p>","DOI":"10.1007\/s00236-020-00383-6","type":"journal-article","created":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T09:05:06Z","timestamp":1626685506000},"page":"451-462","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A faster algorithm for the Birthday Song Singers Synchronization Problem (FSSP) in one-dimensional CA with multiple speeds"],"prefix":"10.1007","volume":"58","author":[{"given":"Thomas","family":"Worsch","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"383_CR1","doi-asserted-by":"crossref","unstructured":"Manzoni, L., Porreca, A.E., Umeo, H.: The firing squad synchronization problem on higher-dimensional CA with multiple updating cycles. In: Fourth International Symposium on Computing and Networking, CANDAR 2016, Hiroshima, Japan, November 22\u201325, 2016, pp. 258\u2013261 (2016)","DOI":"10.1109\/CANDAR.2016.0053"},{"key":"383_CR2","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.tcs.2014.08.011","volume":"559","author":"L Manzoni","year":"2014","unstructured":"Manzoni, L., Umeo, H.: The firing squad synchronization problem on CA with multiple updating cycles. Theor. Comput. Sci. 559, 108\u2013117 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"383_CR3","doi-asserted-by":"crossref","unstructured":"Umeo, H.: Firing squad synchronization problem in cellular automata. In: Encyclopedia of Complexity and Systems Science. Springer, pp. 3537\u20133574 (2009)","DOI":"10.1007\/978-0-387-30440-3_211"},{"issue":"1\u20134","key":"383_CR4","first-page":"393","volume":"171","author":"H Umeo","year":"2020","unstructured":"Umeo, H.: How to synchronize cellular automata\u2014recent developments. Fundam. Inf. 171(1\u20134), 393\u2013419 (2020)","journal-title":"Fundam. Inf."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00383-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-020-00383-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00383-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T09:56:56Z","timestamp":1626688616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-020-00383-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":4,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["383"],"URL":"https:\/\/doi.org\/10.1007\/s00236-020-00383-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"4 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}