{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:23:30Z","timestamp":1743103410120,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_44","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"496-507","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Network Synchronization"],"prefix":"10.1007","author":[{"given":"Darin","family":"Goldstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kojiro","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting straight-line embeddings of planar graph. In: Proc. of the 20th Annual ACM Symp. on Theory of Computing, pp. 426\u2013433 (1988)","DOI":"10.1145\/62212.62254"},{"key":"44_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica\u00a010, 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1006\/jagm.1996.0840","volume":"24","author":"S. Even","year":"1997","unstructured":"Even, S., Litman, A., Winkler, P.: Computing with snakes in directed networks of automata. J. Algorithms\u00a024(1), 158\u2013170 (1997)","journal-title":"J. Algorithms"},{"key":"44_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"44_CR5","unstructured":"Goldstein, D., Meyer, N.: The wake up and report problem is asymptotically time-equivalent to the firing squad synchronization problem. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 2002, pp. 6\u20138 (2002)"},{"key":"44_CR6","unstructured":"Goto, E.: A minimal time solution of the firing squad problem. In: Course Notes for Applied Mathematics 298, Harvard University, pp. 52\u201359 (1962)"},{"issue":"1","key":"44_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0304-3975(81)90004-9","volume":"14","author":"N. Honda","year":"1981","unstructured":"Honda, N., Nishitani, Y.: The firing squad synchronization problem for graphs. Theoretical Computer Science\u00a014(1), 39\u201361 (1981)","journal-title":"Theoretical Computer Science"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Jiang, T.: The synchronization of nonuniform networks of finite automata. In: Proc. of the 30th Annual ACM Symp. on Foundations of Computer Science, pp. 376\u2013381 (1989)","DOI":"10.1109\/SFCS.1989.63506"},{"key":"44_CR9","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/0890-5401(92)90036-F","volume":"97","author":"T. Jiang","year":"1992","unstructured":"Jiang, T.: The synchronization of nonuniform networks of finite automata. Information and Computation\u00a097, 234\u2013261 (1992)","journal-title":"Information and Computation"},{"issue":"3","key":"44_CR10","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(78)90011-9","volume":"17","author":"K. Kobayashi","year":"1978","unstructured":"Kobayashi, K.: The firing squad synchronization problems for a class of polyautomata networks. J. Comput. System Sci.\u00a017(3), 300\u2013318 (1978)","journal-title":"J. Comput. System Sci."},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(78)90046-4","volume":"7","author":"K. Kobayashi","year":"1978","unstructured":"Kobayashi, K.: On the minimal firing time of the firing squad synchronization problem for polyautomata networks. Theoretical Computer Science\u00a07, 149\u2013167 (1978)","journal-title":"Theoretical Computer Science"},{"key":"44_CR12","unstructured":"Kobayashi, K.: A complexity-theoretical approach to the firing squad synchronization problem. In: Proceedings of JIM 1999 (Journ\u00e9e de l\u2019Informatique Messine (Days of Metz Informatics)), NP-Completeness and Parallelism, Metz University, Institute of Technology, May 17\u201318\u00a0(1999)"},{"key":"44_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0304-3975(99)00332-1","volume":"259","author":"K. Kobayashi","year":"2001","unstructured":"Kobayashi, K.: On time optimal solutions of the firing squad synchronization problem for two-dimensional paths. Theoretical Computer Science\u00a0259, 129\u2013143 (2001)","journal-title":"Theoretical Computer Science"},{"key":"44_CR14","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(87)90124-1","volume":"50","author":"J. Mazoyer","year":"1987","unstructured":"Mazoyer, J.: A six states minimal time solution to the firing squad synchronization problem. Theoretical Computer Science\u00a050, 183\u2013238 (1987)","journal-title":"Theoretical Computer Science"},{"key":"44_CR15","series-title":"Lecture Notes in Computer Science","volume-title":"Automata Networks","author":"J. Mazoyer","year":"1988","unstructured":"Mazoyer, J.: An overview of the firing synchronization problem. In: Choffrut, C. (ed.) LITP 1986. LNCS, vol.\u00a0316, Springer, Heidelberg (1988)"},{"key":"44_CR16","volume-title":"Computation: Finite and Infinite Machines","author":"M. Minsky","year":"1967","unstructured":"Minsky, M.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)"},{"key":"44_CR17","volume-title":"Sequential Machines, Selected Papers","author":"E.F. Moore","year":"1962","unstructured":"Moore, E.F.: Sequential Machines, Selected Papers. Addison Wesley, Reading (1962)"},{"key":"44_CR18","doi-asserted-by":"crossref","unstructured":": Faster computation on directed networks of automata. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, Ottawa, Ontario, Canada, August 2\u201323, pp. 38\u201346 (1995)","DOI":"10.1145\/224964.224969"},{"key":"44_CR19","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S0019-9958(66)90110-0","volume":"9","author":"A. Waksman","year":"1966","unstructured":"Waksman, A.: An optimum solution to the firing squad synchronization problem. Information and Control\u00a09, 66\u201378 (1966)","journal-title":"Information and Control"},{"issue":"2","key":"44_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0304-3975(94)90045-0","volume":"127","author":"J.-B. Yunes","year":"1993","unstructured":"Yunes, J.-B.: Seven states solutions to the firing squad synchronization problem. Theoretical Computer Science\u00a0127(2), 313\u2013332 (1993)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:52:25Z","timestamp":1740261145000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}