{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:50:24Z","timestamp":1767340224870,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031099922"},{"type":"electronic","value":"9783031099939"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09993-9_7","type":"book-chapter","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T20:12:42Z","timestamp":1656101562000},"page":"116-134","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Meta-Theorem for\u00a0Distributed Certification"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,25]]},"reference":[{"issue":"1\u20132","key":"7_CR1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0304-3975(96)00286-1","volume":"186","author":"Y Afek","year":"1997","unstructured":"Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186(1\u20132), 199\u2013229 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: 32nd Symposium on Foundations of Computer Science (FOCS), pp. 268\u2013277 (1991)","DOI":"10.1109\/SFCS.1991.185378"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jcss.2018.05.004","volume":"97","author":"A Balliu","year":"2018","unstructured":"Balliu, A., D\u2019Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? J. Comput. Syst. Sci. 97, 106\u2013120 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Bick, A., Kol, G., Oshman, R.: Distributed zero-knowledge proofs over networks. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2022)","DOI":"10.1137\/1.9781611977073.97"},{"key":"7_CR5","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 344 of LNCS, pp. 1\u201310. Springer, 1988. https:\/\/doi.org\/10.1007\/3-540-50728-0_32","DOI":"10.1007\/3-540-50728-0_32"},{"issue":"1\u20132","key":"7_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width I: tractable FO model checking. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 16\u201319 November 2020, Durham, NC, USA, pp. 601\u2013612. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5&6), 555\u2013581 (1992)","DOI":"10.1007\/BF01758777"},{"key":"7_CR9","unstructured":"Bousquet, N., Feuilloley, L., Pierron, T.: Brief announcement: local certification of graph decompositions and applications to minor-free classes. In: 35th International Symposium on Distributed Computing (DISC), vol. 209 of LIPIcs, pp. 49:1\u201349:4. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"7_CR10","unstructured":"Bousquet, N., Feuilloley, L., Pierron, T.: Local certification of MSO properties for bounded treedepth graphs. arXiv:2110.01936 (2021)"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.tcs.2018.08.020","volume":"811","author":"K Censor-Hillel","year":"2020","unstructured":"Censor-Hillel, K., Paz, A., Perry, M.: Approximate proof-labeling schemes. Theor. Comput. Sci. 811, 112\u2013124 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Cambridge University Press, Cambridge (2012)","DOI":"10.1017\/CBO9780511977619"},{"key":"7_CR14","unstructured":"Emek, Y., Gil, Y.: Twenty-two new approximate proof labeling schemes. In: 34th International Symposium on Distributed Computing (DISC), vol. 179 of LIPIcs, pp. 20:1\u201320:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2020.12.017","volume":"856","author":"L Feuilloley","year":"2021","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. Theor. Comput. Sci. 856, 51\u201367 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35:1\u201335:26 (2013)","DOI":"10.1145\/2499228"},{"issue":"3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00446-018-0340-8","volume":"32","author":"P Fraigniaud","year":"2019","unstructured":"Fraigniaud, P., Patt-Shamir, B., Perry, M.: Randomized proof-labeling schemes. Distrib. Comput. 32(3), 217\u2013234 (2019)","journal-title":"Distrib. Comput."},{"issue":"1","key":"7_CR18","first-page":"1","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1\u201333 (2016)","journal-title":"Theory Comput."},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM 64(3), 17:1\u201317:32 (2017)","DOI":"10.1145\/3051095"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Itkis, G., Levin, L.A.: Fast and lean self-stabilizing asynchronous protocols. In: 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 226\u2013239 (1994)","DOI":"10.1109\/SFCS.1994.365691"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 255\u2013264 (2018)","DOI":"10.1145\/3212734.3212771"},{"issue":"4","key":"7_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Liedloff, M., Montealegre, P., Todinca, I.: Beyond classes of graphs with \u201cfew\u201d minimal separators: FPT results through potential maximal cliques. Algorithmica 81(3), 986\u20131005 (2019)","DOI":"10.1007\/s00453-018-0453-2"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1096\u20131115 (2020)","DOI":"10.1137\/1.9781611975994.67"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984)","DOI":"10.1016\/0095-8956(84)90013-3"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09993-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T19:27:33Z","timestamp":1727465253000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09993-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031099922","9783031099939"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09993-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"25 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paderborn","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2022.cs.uni-paderborn.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}