{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:19Z","timestamp":1761611299994},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540564027"},{"type":"electronic","value":"9783540475545"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56402-0_58","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:10:15Z","timestamp":1330254615000},"page":"333-345","source":"Crossref","is-referenced-by-count":12,"title":["The power and the limitations of local computations on graphs"],"prefix":"10.1007","author":[{"given":"Igor","family":"Litovsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yves","family":"M\u00e9tivier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wies\u0142aw","family":"Zielonka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"29_CR1","unstructured":"D.Angluin: Local and global properties in networks of processors. in Proceedings of the 12th STOC (1980) 82\u201393"},{"key":"29_CR2","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0095-8956(81)90062-9","volume":"B 30","author":"D. Angluin","year":"1981","unstructured":"D.Angluin and A.Gardiner: Finite common coverings of pairs of regular graphs. J. Combin. Theory Ser. B 30 (1981) 184\u2013187","journal-title":"J. Combin. Theory Ser."},{"key":"29_CR3","unstructured":"O.Baudon: Cabri-graphes, un cahier de brouillon interactif pour la th\u00e9orie des graphes. Ph.D. Universit\u00e9 Joseph Fourier, Grenoble I (1990)"},{"key":"29_CR4","volume-title":"Graphes et Hypergraphes","author":"C. Berge","year":"1970","unstructured":"C.Berge: Graphes et Hypergraphes. Dunod, Paris (1970)"},{"key":"29_CR5","first-page":"388","volume":"264","author":"J. Berstel","year":"1967","unstructured":"J.Berstel: R\u00e9solution, par un r\u00e9seau d'automates, du probl\u00e8me des arborescences dans un graphe. C.R. Acad. Sc. Paris, S\u00e9rie A, t.264 (1967) 388\u2013390","journal-title":"C.R. Acad. Sc. Paris, S\u00e9rie A"},{"key":"29_CR6","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-52292-1_7","volume":"411","author":"M. Billaud","year":"1989","unstructured":"M.Billaud, P.Lafon, Y.M\u00e9tivier and E.Sopena: Graph Rewriting Systems with Priorities. Lecture Notes in Comput. Sci 411 (1989) 94\u2013106","journal-title":"Lecture Notes in Comput. Sci"},{"key":"29_CR7","first-page":"161","volume":"36","author":"B. Courcelle","year":"1988","unstructured":"B.Courcelle: Some applications of logic, of universal algebra, and of category theory to the theory of graph transformations. EATCS Bulletin 36 (1988) 161\u2013213","journal-title":"EATCS Bulletin"},{"key":"29_CR8","unstructured":"B.Courcelle: Recognizable sets of unrooted trees. in Definability and recognizability of sets of trees (to appear) Elsevier"},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/BF01843568","volume":"1","author":"M.J. Fisher","year":"1986","unstructured":"M.J.Fisher, N.A.Lynch and M.Merritt: Easy impossibility proofs for distributed consensus problems. Distributed Computing 1 (1986) 26\u201339","journal-title":"Distributed Computing"},{"issue":"1","key":"29_CR10","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1109\/TC.1982.1675885","volume":"C31","author":"H. Garcia-Molina","year":"1982","unstructured":"H.Garcia-Molina: Election in a distributed computing System. IEEE Trans. Comput. C31, 1 (1982) 48\u201359","journal-title":"IEEE Trans. Comput."},{"key":"29_CR11","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0095-8956(82)90042-9","volume":"B 33","author":"F.T. Leighton","year":"1982","unstructured":"F.T.Leighton: Finite common coverings of graphs. J. Combin. Theory Ser. B 33 (1982) 231\u2013238","journal-title":"J. Combin. Theory Ser."},{"key":"29_CR12","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/BFb0017412","volume":"532","author":"I. Litovsky","year":"1991","unstructured":"I.Litovsky and Y.M\u00e9tivier: Computing with Graph Relabelling Systems with Priorities. Fourth International Workshop on Graph Grammars and their Applications to Computer Science, Bremen, Lecture Notes in Comput. Sci 532 (1991) 549\u2013563","journal-title":"Lecture Notes in Comput. Sci"},{"key":"29_CR13","first-page":"90","volume":"I","author":"I. Litovsky","year":"1990","unstructured":"I.Litovsky and Y.M\u00e9tivier: Computing trees with graph rewriting systems with priorities. Internal report, University Bordeaux I 900\u201385 (1990)","journal-title":"Internal report, University Bordeaux"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"I.Litovsky, Y.M\u00e9tivier and E.Sopena: Definition and comparison of local computations on graphs and networks. Internal report, University Bordeaux I (1991) (\u00e0 paraitre in Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci)","DOI":"10.1007\/3-540-55808-X_35"},{"key":"29_CR15","first-page":"91","volume":"I","author":"I. Litovsky","year":"1991","unstructured":"I.Litovsky, Y.M\u00e9tivier and W.Zielonka: The power and the limitations of local computations on graphs. Internal report, University Bordeaux I 9191\u201331 (1991)","journal-title":"Internal report, University Bordeaux"},{"key":"29_CR16","first-page":"90","volume":"I","author":"A. Mazurkiewicz","year":"1990","unstructured":"A.Mazurkiewicz: Elections in planar graphs. Internal report, University Bordeaux I 90\u2013105 (1990)","journal-title":"Internal report, University Bordeaux"},{"key":"29_CR17","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0190(88)90193-7","volume":"28","author":"A. Mazurkiewicz","year":"1988","unstructured":"A.Mazurkiewicz: Solvability of asynchronous ranking problem. Inform. Proc. letters 28 (1988) 221\u2013224","journal-title":"Inform. Proc. letters"},{"key":"29_CR18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/B978-1-4832-3187-7.50019-2","volume-title":"Intelligent graphs. Graph theory and computing","author":"P. Rosenstiehl","year":"1972","unstructured":"P.Rosenstiehl, J.R.Fiksel and A.Holliger: Intelligent graphs. Graph theory and computing (1972) 219\u2013265 Ronald C. Read New York"}],"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\/3-540-56402-0_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:03:47Z","timestamp":1605647027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56402-0_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540564027","9783540475545"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-56402-0_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}