{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:10:38Z","timestamp":1753438238539},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_14","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"154-165","source":"Crossref","is-referenced-by-count":5,"title":["Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"St\u00e9phane","family":"Grumbach","sequence":"first","affiliation":[]},{"given":"Zhilin","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","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. Wiley Interscience, Hoboken (2004)"},{"issue":"5","key":"14_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.ipl.2008.05.016","volume":"108","author":"C. Boulinier","year":"2008","unstructured":"Boulinier, C., Datta, A.K., Larmore, L.L., Petit, F.: Space efficient and time optimal distributed BFS tree construction. Inf. Process. Lett.\u00a0108(5), 273\u2013278 (2008)","journal-title":"Inf. Process. Lett."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: ACM STOC (1993)","DOI":"10.1145\/167088.167161"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree Spanners. SIAM J. Discret. Math.\u00a08(3), 359\u2013387 (1995)","journal-title":"SIAM J. Discret. Math."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 193\u2013242. Elsevier and MIT Press (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph algebras and monadic second-order logic. To be published by Cambridge University Press (2008) (in preparation)","DOI":"10.1017\/CBO9780511977619"},{"key":"14_CR7","volume-title":"Finite model theory","author":"H.D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite model theory. Springer, Heidelberg (1999)"},{"issue":"6","key":"14_CR8","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J. Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM\u00a049(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"issue":"6","key":"14_CR9","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM\u00a048(6), 1184\u20131206 (2001)","journal-title":"J. ACM"},{"key":"14_CR10","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"1","key":"14_CR11","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin","year":"1995","unstructured":"Fagin, R., Stockmeyer, L.J., Vardi, M.Y.: On a monadic NP vs monadic co-NP. Inf. Comput.\u00a0120(1), 78\u201392 (1995)","journal-title":"Inf. Comput."},{"key":"14_CR12","volume-title":"Proceedings of the Herbrand Symposium, Logic Colloquium 1981","author":"H. Gaifman","year":"1982","unstructured":"Gaifman, H.: On local and non-local properties. In: Proceedings of the Herbrand Symposium, Logic Colloquium 1981, North-Holland, Amsterdam (1982)"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00224-003-1062-1","volume":"37","author":"E. Godard","year":"2004","unstructured":"Godard, E., M\u00e9tivier, Y., Muscholl, A.: Characterizations of classes of graphs recognizable by local computations. Theory Comput. Syst.\u00a037(2), 249\u2013293 (2004)","journal-title":"Theory Comput. Syst."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Otto, M.: Inductive definability with counting on finite structures. In: Computer Science Logic, CSL, pp. 231\u2013247 (1992)","DOI":"10.1007\/3-540-56992-8_15"},{"issue":"1","key":"14_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-3975(95)00026-S","volume":"149","author":"S. Grumbach","year":"1995","unstructured":"Grumbach, S., Tollu, C.: On the expressive power of counting. Theor. Comput. Sci.\u00a0149(1), 67\u201399 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR16","unstructured":"Grumbach, S., Wu, Z.: On the distributed evaluation of MSO on graphs (2009) (manuscript)"},{"issue":"3","key":"14_CR17","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"Immerman, N.: Expressibility and parallel complexity. SIAM J. Comput.\u00a018(3), 625\u2013638 (1989)","journal-title":"SIAM J. Comput."},{"issue":"1-3","key":"14_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.apal.2004.01.004","volume":"128","author":"H.J. Keisler","year":"2004","unstructured":"Keisler, H.J., Lotfallah, W.B.: Shrinking games and local formulas. Ann. Pure Appl. Logic\u00a0128(1-3), 215\u2013225 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally. In: ACM PODC (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Seventeenth ACM-SIAM SODA (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Libkin, L.: On the forms of locality over finite models. In: LICS, pp. 204\u2013215 (1997)","DOI":"10.1109\/LICS.1997.614948"},{"issue":"1","key":"14_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"14_CR23","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput.\u00a024(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"147","DOI":"10.2307\/2275602","volume":"61","author":"M. Otto","year":"1996","unstructured":"Otto, M.: The expressive power of fixed-point logic with counting. J. Symb. Log.\u00a061(1), 147\u2013176 (1996)","journal-title":"J. Symb. Log."},{"key":"14_CR25","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed computing: a locality-sensitive approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Seese, D.: Linear time computable problems and logical descriptions. Electr. Notes Theor. Comput. Sci.\u00a02 (1995)","DOI":"10.1016\/S1571-0661(05)80203-8"},{"issue":"1","key":"14_CR27","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Systems Theory\u00a02(1), 57\u201381 (1968)","journal-title":"Math. Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:19Z","timestamp":1606185619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}