{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T19:23:38Z","timestamp":1773948218762,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,1,3]],"date-time":"2006-01-03T00:00:00Z","timestamp":1136246400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2006,1,3]],"date-time":"2006-01-03T00:00:00Z","timestamp":1136246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s00446-005-0138-3","type":"journal-article","created":{"date-parts":[[2005,12,28]],"date-time":"2005-12-28T05:06:56Z","timestamp":1135746416000},"page":"235-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":363,"title":["Computation in networks of passively mobile finite-state sensors"],"prefix":"10.1007","volume":"18","author":[{"given":"Dana","family":"Angluin","sequence":"first","affiliation":[]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[]},{"given":"Zo\u00eb","family":"Diamadi","sequence":"additional","affiliation":[]},{"given":"Michael J.","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Ren\u00e9","family":"Peralta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,1,3]]},"reference":[{"key":"138_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Viktor K. Prasanna, Sitharama Iyengar, Paul Spirakis and Matt Welsh (eds.), Distributed Computing in Sensor Systems: First IEEE International Conference (2005). Lecture Notes in Computer Science 3560, 63\u201374 (June\/July, 2005) Proceedings Marina del Rey, CA, USA","DOI":"10.1007\/11502593_8"},{"key":"138_CR2","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn automata. Tech. Rep. YALEU\/DCS\/TR\u20131280, Yale University Department of Computer Science (2003)"},{"key":"138_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0304-3975(92)90185-I","volume":"96","author":"G. Berry","year":"1992","unstructured":"Berry, G., Boudol, G.: The chemical abstract machine. Theor. Comp. Sci. 96, 217\u2013248 (1992)","journal-title":"Theor. Comp. Sci."},{"issue":"2","key":"138_CR4","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/322374.322380","volume":"30","author":"D. Brand","year":"1983","unstructured":"Brand, D., Zafiropulo, P.: On communicating finite-state machines. J. ACM 30(2), 323\u2013342 (1983)","journal-title":"J. ACM"},{"key":"138_CR5","doi-asserted-by":"crossref","unstructured":"Diamadi, Z., Fischer, M.J.: A simple game for the study of trust in distributed systems. Wuhan Univ. J. Natur. Sci. 6(1\u20132), 72\u201382 (2001). Also appears as Yale Technical Report TR\u20131207, January 2001, available at URL ftp:\/\/ftp.cs.yale.edu\/pub\/TR\/tr1207.ps","DOI":"10.1007\/BF03160228"},{"key":"138_CR6","doi-asserted-by":"crossref","unstructured":"Esparza, J.: Decidability and complexity of Petri net problems-an introduction. In: Rozenberg, G., Reisig, W., (eds.) Lectures on Petri Nets I: Basic models, pp. 374\u2013428. Springer Verlag (1998). Published as LNCS 1491","DOI":"10.1007\/3-540-65306-6_20"},{"issue":"3","key":"138_CR7","first-page":"143","volume":"30","author":"J. Esparza","year":"1994","unstructured":"Esparza, J., Nielsen, M.: Decibility issues for Petri nets\u2014a survey. J. Inform. Process. Cybern. 30(3), 143\u2013160 (1994)","journal-title":"J. Inform. Process. Cybern."},{"key":"138_CR8","doi-asserted-by":"crossref","unstructured":"Fang, Q., Zhao, F., Guibas, L.: Lightweight sensing and communication protocols for target enumeration and aggregation. In: Proceedings of the 4th ACM International Symposium on Mobile ad hoc Networking & Computing, pp. 165\u2013176. ACM Press (2003)","DOI":"10.1145\/778415.778436"},{"key":"138_CR9","unstructured":"Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. In: Complexity of Computation, SIAM-AMS Proceedings, vol. VII, pp. 27\u201341. American Mathematical Society (1974)"},{"key":"138_CR10","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas, and languages. Pac. J. Math. 16, 285\u2013296 (1966)","journal-title":"Pac. J. Math."},{"issue":"4","key":"138_CR11","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1109\/TNET.2002.801403","volume":"10","author":"M. Grossglauser","year":"2002","unstructured":"Grossglauser, M., Tse, D.N.C.: Mobility increases the capacity of ad hoc wireless networks. IEEE\/ACM Transac. Networking 10(4), 477\u2013486 (2002)","journal-title":"IEEE\/ACM Transac. Networking"},{"issue":"2\u20133","key":"138_CR12","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.tcs.2003.10.028","volume":"312","author":"O.H. Ibarra","year":"2004","unstructured":"Ibarra, O.H., Dang, Z., Egecioglu, O.: Catalytic p systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 312(2\u20133), 379\u2013399 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"138_CR13","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"key":"138_CR14","doi-asserted-by":"crossref","unstructured":"Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: a scalable and robust communication paradigm for sensor networks. In: Proceedings of the 6th Annual International Conference on Mobile computing and networking, pp. 56\u201367. ACM Press (2000)","DOI":"10.1145\/345910.345920"},{"key":"138_CR15","doi-asserted-by":"crossref","unstructured":"Kracht, M.: The Mathematics of Language, Studies in Generative Grammar, vol. 63. Mouton de Gruyter (2003). ISBN 3-11-017620-3","DOI":"10.1515\/9783110895667"},{"key":"138_CR16","doi-asserted-by":"crossref","unstructured":"Madden, S.R., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: A Tiny AGgregation service for ad-hoc sensor networks (December, 2002). In OSDI 2002: Fifth Symposium on Operating Systems Design and Implementation","DOI":"10.1145\/1060289.1060303"},{"key":"138_CR17","doi-asserted-by":"crossref","unstructured":"Milner, R.: Bigraphical reactive systems: basic theory. Tech. rep., University of Cambridge (2001). UCAM-CL-TR-523","DOI":"10.1007\/3-540-44685-0_2"},{"key":"138_CR18","volume-title":"Computation: Finite and Infinite Machines. Prentice-Hall Series in Automatic Computation","author":"M.L. Minsky","year":"1967","unstructured":"Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Inc., Englewood Cliffs, N.J. (1967)"},{"key":"138_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9452-5","volume-title":"Mathematical Logic","author":"J.D. Monk","year":"1976","unstructured":"Monk, J.D.: Mathematical Logic. Springer, Berlin, Heidelberg (1976)"},{"key":"138_CR20","unstructured":"von Neumann, J.: Theory and organization of complicated automata. In: A.W. Burks (ed.) Theory of Self-Reproducing Automata [by] John von Neumann, pp. 29\u201387 (Part One). University of Illinois Press, Urbana (1949). Based on transcripts of lectures delivered at the University of Illinois, in December 1949. Edited for publication by A.W. Burks"},{"issue":"4","key":"138_CR21","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966).","journal-title":"J. ACM"},{"key":"138_CR22","unstructured":"Presburger, M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes-Rendus du I Congr\u00e8s de Math\u00e9maticiens des Pays Slaves, pp. 92\u2013101. Warszawa (1929)"},{"key":"138_CR23","doi-asserted-by":"crossref","unstructured":"Volzer, H.: Randomized non-sequential processes. In: Proceedings of CONCUR 2001-Concurrency Theory, pp. 184\u2013201 (2001)","DOI":"10.1007\/3-540-44685-0_13"},{"issue":"8","key":"138_CR24","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1109\/JPROC.2003.814921","volume":"91","author":"F. Zhao","year":"2003","unstructured":"Zhao, F., Liu, J., Liu, J., Guibas, L., Reich, J.: Collaborative signal and information processing: An information directed approach. Proc. IEEE 91(8), 1199\u20131209 (2003)","journal-title":"Proc. IEEE"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-005-0138-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-005-0138-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-005-0138-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-005-0138-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T01:39:48Z","timestamp":1652492388000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-005-0138-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,3]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["138"],"URL":"https:\/\/doi.org\/10.1007\/s00446-005-0138-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1,3]]},"assertion":[{"value":"23 September 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2006","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}