{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:42:19Z","timestamp":1782970939059,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T00:00:00Z","timestamp":1698192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T00:00:00Z","timestamp":1698192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB210005"],"award-info":[{"award-number":["FB210005"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB210005"],"award-info":[{"award-number":["FB210005"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1230599"],"award-info":[{"award-number":["1230599"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1220142"],"award-info":[{"award-number":["1220142"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s00453-023-01185-1","type":"journal-article","created":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T12:02:01Z","timestamp":1698235321000},"page":"585-612","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Meta-Theorem for Distributed Certification"],"prefix":"10.1007","volume":"86","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,10,25]]},"reference":[{"issue":"1\u20132","key":"1185_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":"1185_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":"1185_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":"1185_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":"1185_CR5","doi-asserted-by":"crossref","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)","DOI":"10.1007\/3-540-50728-0_32"},{"issue":"1\u20132","key":"1185_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":"1185_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, Durham, NC, USA, November 16-19, 2020, pp. 601\u2013612. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00062"},{"issue":"5 &6","key":"1185_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","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)","journal-title":"Algorithmica"},{"key":"1185_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), volume 209 of LIPIcs, pages 49:1\u201349:4. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2021)"},{"key":"1185_CR10","unstructured":"Bousquet, N., Feuilloley, L., Pierron, T.: What can be certified compactly? arXiv:2202.06065 (2022)"},{"key":"1185_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."},{"issue":"1","key":"1185_CR12","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1185_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Cambridge University Press, Cambridge (2012)"},{"key":"1185_CR14","unstructured":"Emek, Y., Gil, Y.: Twenty-two new approximate proof labeling schemes. In: 34th International Symposium on Distributed Computing (DISC), volume 179 of LIPIcs, pp. 20:1\u201320:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1185_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."},{"issue":"1","key":"1185_CR16","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/140964801","volume":"44","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and CMSO. SIAM J. Comput. 44(1), 54\u201387 (2015)","journal-title":"SIAM J. Comput."},{"key":"1185_CR17","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":"1185_CR18","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. Distributed Comput. 32(3), 217\u2013234 (2019)","journal-title":"Distributed Comput."},{"issue":"1","key":"1185_CR19","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":"1185_CR20","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":"1185_CR21","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":"1185_CR22","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":"1185_CR23","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."},{"issue":"3","key":"1185_CR24","doi-asserted-by":"publisher","first-page":"986","DOI":"10.1007\/s00453-018-0453-2","volume":"81","author":"M Liedloff","year":"2019","unstructured":"Liedloff, M., Montealegre, P., Todinca, I.: Beyond classes of graphs with \u201cfew\u2019\u2019 minimal separators: FPT results through potential maximal cliques. Algorithmica 81(3), 986\u20131005 (2019)","journal-title":"Algorithmica"},{"key":"1185_CR25","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\u2013115 (2020)","DOI":"10.1137\/1.9781611975994.67"},{"key":"1185_CR26","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":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01185-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01185-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01185-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,31]],"date-time":"2024-10-31T20:12:42Z","timestamp":1730405562000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01185-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,25]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1185"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01185-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,25]]},"assertion":[{"value":"15 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"No applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}]}}