{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:44Z","timestamp":1760202704282,"version":"3.41.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319252575"},{"type":"electronic","value":"9783319252582"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_20","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T07:10:18Z","timestamp":1445238618000},"page":"285-298","source":"Crossref","is-referenced-by-count":1,"title":["Information Spreading by Mobile Particles on a Line"],"prefix":"10.1007","author":[{"given":"Jurek","family":"Czyzowicz","sequence":"first","affiliation":[]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[]},{"given":"Eduardo","family":"Pacheco","sequence":"additional","affiliation":[]},{"given":"Dominik","family":"Paj\u0105k","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1007\/BF01074110","volume":"96","author":"M. Sevryuk","year":"1993","unstructured":"Sevryuk, M.: Estimate of the number of collisions of n elastic particles on a line. Theoretical and Mathematical Physics\u00a096(1), 818\u2013826 (1993)","journal-title":"Theoretical and Mathematical Physics"},{"issue":"4","key":"20_CR2","doi-asserted-by":"publisher","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.\u00a028(4), 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"20_CR3","doi-asserted-by":"publisher","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. Dist. Comp.\u00a018(4), 235\u2013253 (2006)","journal-title":"Dist. Comp."},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: PODC, pp. 292\u2013299 (2006)","DOI":"10.1145\/1146381.1146425"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Das, S., Flocchini, P., Santoro, N., Yamashita, M.: On the computational power of oblivious robots: forming a series of geometric patterns. In: PODC, pp. 267\u2013276 (2010)","DOI":"10.1145\/1835698.1835761"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-46632-0_10","volume-title":"Algorithms and Computations","author":"P. Flocchini","year":"1999","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 93\u2013102. Springer, Heidelberg (1999)"},{"issue":"4","key":"20_CR7","doi-asserted-by":"publisher","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 Journal on Computing\u00a028(4), 1347\u20131363 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"26","key":"20_CR8","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1016\/j.tcs.2010.01.037","volume":"411","author":"M. Yamashita","year":"2010","unstructured":"Yamashita, M., Suzuki, I.: Characterizing geometric patterns formable by oblivious anonymous mobile robots. TCS\u00a0411(26), 2433\u20132453 (2010)","journal-title":"TCS"},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2008.02.007","volume":"399","author":"R. Cohen","year":"2008","unstructured":"Cohen, R., Peleg, D.: Local spreading algorithms for autonomous robot systems. TCS\u00a0399(1), 71\u201382 (2008)","journal-title":"TCS"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-44693-1_22","volume-title":"STACS 2001","author":"P. Flocchini","year":"2001","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous oblivious robots with limited visibility. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 247\u2013258. Springer, Heidelberg (2001)"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-642-39212-2_45","volume-title":"Automata, Languages, and Programming","author":"J. Czyzowicz","year":"2013","unstructured":"Czyzowicz, J., Kranakis, E., Pacheco, E.: Localization for a system of colliding robots. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol.\u00a07966, pp. 508\u2013519. Springer, Heidelberg (2013)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-33651-5_24","volume-title":"Distributed Computing","author":"J. Czyzowicz","year":"2012","unstructured":"Czyzowicz, J., G\u0105sieniec, L., Kosowski, A., Kranakis, E., Ponce, O.M., Pacheco, E.: Position discovery for a system of bouncing robots. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol.\u00a07611, pp. 341\u2013355. Springer, Heidelberg (2012)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. In: ACM Symposium on Principles of Distributed Computing, PODC 2014, Paris, France, July 15-18, pp. 76\u201385 (2014)","DOI":"10.1145\/2611462.2611466"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C., Spirakis, P.G.: Determining majority in networks with local interactions and very small local memory. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part I. LNCS, vol.\u00a08572, pp. 871\u2013882. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-43948-7_72"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Cao, Y.U., Fukunaga, A.S., Kahng, A.B., Meng, F.: Cooperative mobile robotics: Antecedents and directions. In: Proceedings of the 1995 IEEE\/RSJ International Conference on Intelligent Robots and Systems 1995. \u2018Human Robot Interaction and Cooperative Robots, vol.\u00a01, pp. 226\u2013234. IEEE (1995)","DOI":"10.1109\/IROS.1995.525801"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Dudek, G., Jenkin, M.: Computational principles of mobile robotics. Cambridge University Press (2010)","DOI":"10.1017\/CBO9780511780929"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and mapping directed graphs. In: STOC, pp. 269\u2013278 (1998)","DOI":"10.1145\/276698.276759"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-540-77566-9_20","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"J. Czyzowicz","year":"2008","unstructured":"Czyzowicz, J., Dobrev, S., An, H.-C., Krizanc, D.: The power of tokens: Rendezvous and symmetry detection for two mobile agents in a ring. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 234\u2013246. Springer, Heidelberg (2008)"},{"issue":"3","key":"20_CR19","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1007\/BF02188582","volume":"74","author":"T. Murphy","year":"1994","unstructured":"Murphy, T.: Dynamics of hard rods in one dimension. Journal of Statistical Physics\u00a074(3), 889\u2013901 (1994)","journal-title":"Journal of Statistical Physics"},{"issue":"10","key":"20_CR20","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1103\/PhysRev.50.955","volume":"50","author":"L. Tonks","year":"1936","unstructured":"Tonks, L.: The complete equation of state of one, two and three-dimensional gases of hard elastic spheres. Physical Review\u00a050(10), 955 (1936)","journal-title":"Physical Review"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Wylie, J., Yang, R., Zhang, Q.: Periodic orbits of inelastic particles on a ring. Physical Review E 86, 026601(2) (2012)","DOI":"10.1103\/PhysRevE.86.026601"},{"issue":"2","key":"20_CR22","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/S003614450342658X","volume":"47","author":"B. Cooley","year":"2005","unstructured":"Cooley, B., Newton, P.: Iterated impact dynamics of n-beads on a ring. SIAM Rev.\u00a047(2), 273\u2013300 (2005)","journal-title":"SIAM Rev."},{"issue":"5-6","key":"20_CR23","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1007\/BF01049961","volume":"71","author":"T. Murphy","year":"1993","unstructured":"Murphy, T., Cohen, E.: Maximum number of collisions among identical hard spheres. Journal of Statistical Physics\u00a071(5-6), 1063\u20131080 (1993)","journal-title":"Journal of Statistical Physics"},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-642-32589-2_37","volume-title":"Mathematical Foundations of Computer Science 2012","author":"T. Friedetzky","year":"2012","unstructured":"Friedetzky, T., G\u0105sieniec, L., Gorry, T., Martin, R.: Observe and remain silent (Communication-less agent location discovery). In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 407\u2013418. Springer, Heidelberg (2012)"},{"key":"20_CR25","unstructured":"Chan, T.M.: Remarks on k-level algorithms in the plane. Manuscript, Univ. of Waterloo (1999)"},{"key":"20_CR26","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel sequences and their geometric applications. Cambridge University Press (1995)"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, P., Lov\u00e1sz, L., Simmons, A., Straus, E.G.: Dissection graphs of planar point sets. A Survey of Combinatorial Theory, 139\u2013149 (1973)","DOI":"10.1016\/B978-0-7204-2262-7.50018-1"},{"key":"20_CR28","first-page":"107","volume":"14","author":"L. Lov\u00e1sz","year":"1971","unstructured":"Lov\u00e1sz, L.: On the number of halving lines. Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s, Sec. Math.\u00a014, 107\u2013108 (1971)","journal-title":"Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s, Sec. Math."},{"issue":"3","key":"20_CR29","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T.K. Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar k-sets and related problems. Discrete & Computational Geometry\u00a019(3), 373\u2013382 (1998)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"20_CR30","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s004540010022","volume":"26","author":"G. T\u00f3th","year":"2001","unstructured":"T\u00f3th, G.: Point sets with many k-sets. Discrete & Computational Geometry\u00a026(2), 187\u2013194 (2001)","journal-title":"Discrete & Computational Geometry"},{"key":"20_CR31","doi-asserted-by":"crossref","unstructured":"Gregory, R.: Classical mechanics. Cambridge University Press (2006)","DOI":"10.1017\/CBO9780511803789"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Everett, H., Robert, J.M., Van Kreveld, M.: An optimal algorithm for the (\u2264\u2009k)-levels, with applications to separation and transversal problems. In: Proceedings of the Ninth Annual Symposium on Computational Geometry, ACM, pp. 38\u201346 (1993)","DOI":"10.1145\/160985.160994"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25258-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T02:17:37Z","timestamp":1748657857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}