{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T18:58:16Z","timestamp":1768676296498,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538416","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"131-140","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs"],"prefix":"10.1145","author":[{"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[{"name":"Univ Lyon, CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, Villeurbanne, France"}]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[{"name":"Univ Lyon, CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, Villeurbanne, France"}]},{"given":"Th\u00e9o","family":"Pierron","sequence":"additional","affiliation":[{"name":"Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, UMR5205, Villeurbanne, France"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_2_2_1","volume-title":"A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1--2):1--45","author":"Bodlaender Hans L.","year":"1998","unstructured":"Hans L. Bodlaender . A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1--2):1--45 , 1998 . Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1--2):1--45, 1998."},{"key":"e_1_3_2_2_3_1","first-page":"500","volume-title":"16th International Conference, RTA 2005","volume":"3467","author":"Boneva Iovka","year":"2005","unstructured":"Iovka Boneva and Jean-Marc Talbot . Automata and logics for unranked and unordered trees. In J\u00fcrgen Giesl, editor, Term Rewriting and Applications , 16th International Conference, RTA 2005 , volume 3467 , pages 500 -- 515 , 2005 . Iovka Boneva and Jean-Marc Talbot. Automata and logics for unranked and unordered trees. In J\u00fcrgen Giesl, editor, Term Rewriting and Applications, 16th International Conference, RTA 2005, volume 3467, pages 500--515, 2005."},{"key":"e_1_3_2_2_4_1","first-page":"1","volume-title":"25th International Conference on Principles of Distributed Systems, OPODIS 2021","volume":"217","author":"Bousquet Nicolas","year":"2021","unstructured":"Nicolas Bousquet , Laurent Feuilloley , and Th\u00e9o Pierron . Local certification of graph decompositions and applications to minor-free classes . In 25th International Conference on Principles of Distributed Systems, OPODIS 2021 , volume 217 of LIPIcs, pages 22: 1 -- 22 :17, 2021 . Nicolas Bousquet, Laurent Feuilloley, and Th\u00e9o Pierron. Local certification of graph decompositions and applications to minor-free classes. In 25th International Conference on Principles of Distributed Systems, OPODIS 2021, volume 217 of LIPIcs, pages 22:1--22:17, 2021."},{"key":"e_1_3_2_2_5_1","volume-title":"Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1--6)","author":"B\u00fcchi J Richard","year":"1960","unstructured":"J Richard B\u00fcchi . Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1--6) , 1960 . J Richard B\u00fcchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1--6), 1960."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.08.020"},{"key":"e_1_3_2_2_7_1","volume-title":"28th International Colloquium, SIROCCO 2021","volume":"12810","author":"Chang Yi-Jun","year":"2021","unstructured":"Yi-Jun Chang , Jan Studen\u00fd , and Jukka Suomela . Distributed graph problems through an automata-theoretic lens. In Tomasz Jurdzinski and Stefan Schmid, editors, Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021 , volume 12810 of Lecture Notes in Computer Science, pages 31--49 , 2021 . Yi-Jun Chang, Jan Studen\u00fd, and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. In Tomasz Jurdzinski and Stefan Schmid, editors, Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, volume 12810 of Lecture Notes in Computer Science, pages 31--49, 2021."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_2_9_1","first-page":"1","volume-title":"33rd International Symposium on Distributed Computing, DISC 2019","volume":"146","author":"Crescenzi Pierluigi","year":"2019","unstructured":"Pierluigi Crescenzi , Pierre Fraigniaud , and Ami Paz . Trade-offs in distributed interactive proofs . In 33rd International Symposium on Distributed Computing, DISC 2019 , volume 146 of LIPIcs, pages 13: 1 -- 13 :17, 2019 . Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-offs in distributed interactive proofs. In 33rd International Symposium on Distributed Computing, DISC 2019, volume 146 of LIPIcs, pages 13:1--13:17, 2019."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2946799"},{"key":"e_1_3_2_2_12_1","volume-title":"Planarity is (almost) locally checkable in constant-time. CoRR, abs\/2006.11869","author":"Elek G\u00e1bor","year":"2020","unstructured":"G\u00e1bor Elek . Planarity is (almost) locally checkable in constant-time. CoRR, abs\/2006.11869 , 2020 . G\u00e1bor Elek. Planarity is (almost) locally checkable in constant-time. CoRR, abs\/2006.11869, 2020."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.01.023"},{"key":"e_1_3_2_2_15_1","volume-title":"Testability and local certification of monotone properties in minor-closed classes. CoRR, abs\/2202.00543","author":"Esperet Louis","year":"2022","unstructured":"Louis Esperet and Sergey Norin . Testability and local certification of monotone properties in minor-closed classes. CoRR, abs\/2202.00543 , 2022 . Louis Esperet and Sergey Norin. Testability and local certification of monotone properties in minor-closed classes. CoRR, abs\/2202.00543, 2022."},{"key":"e_1_3_2_2_16_1","volume-title":"Introduction to local certification. Discret. Math. Theor. Comput. Sci., 23(3)","author":"Feuilloley Laurent","year":"2021","unstructured":"Laurent Feuilloley . Introduction to local certification. Discret. Math. Theor. Comput. Sci., 23(3) , 2021 . Laurent Feuilloley. Introduction to local certification. Discret. Math. Theor. Comput. Sci., 23(3), 2021."},{"key":"e_1_3_2_2_17_1","first-page":"119","article-title":"Survey of distributed decision","author":"Feuilloley Laurent","year":"2016","unstructured":"Laurent Feuilloley and Pierre Fraigniaud . Survey of distributed decision . Bull. EATCS , 119 , 2016 . Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bull. EATCS, 119, 2016.","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00386-z"},{"key":"e_1_3_2_2_19_1","volume-title":"Local certification of graphs with bounded genus. CoRR, abs\/2007.08084","author":"Feuilloley Laurent","year":"2020","unstructured":"Laurent Feuilloley , Pierre Fraigniaud , Pedro Montealegre , Ivan Rapaport , Eric R\u00e9mila , and Ioan Todinca . Local certification of graphs with bounded genus. CoRR, abs\/2007.08084 , 2020 . Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Eric R\u00e9mila, and Ioan Todinca. Local certification of graphs with bounded genus. CoRR, abs\/2007.08084, 2020."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00823-w"},{"key":"e_1_3_2_2_21_1","first-page":"1","volume-title":"32nd International Symposium on Distributed Computing, DISC 2018","volume":"121","author":"Feuilloley Laurent","year":"2018","unstructured":"Laurent Feuilloley and Juho Hirvonen . Local verification of global proofs . In 32nd International Symposium on Distributed Computing, DISC 2018 , volume 121 of LIPIcs, pages 25: 1 -- 25 :17, 2018 . Laurent Feuilloley and Juho Hirvonen. Local verification of global proofs. In 32nd International Symposium on Distributed Computing, DISC 2018, volume 121 of LIPIcs, pages 25:1--25:17, 2018."},{"key":"e_1_3_2_2_22_1","volume-title":"A meta- theorem for distributed certification. CoRR, abs\/2112.03195","author":"Fraigniaud Pierre","year":"2021","unstructured":"Pierre Fraigniaud , Pedro Montealegre , Ivan Rapaport , and Ioan Todinca . A meta- theorem for distributed certification. CoRR, abs\/2112.03195 , 2021 . Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta- theorem for distributed certification. CoRR, abs\/2112.03195, 2021."},{"key":"e_1_3_2_2_23_1","volume-title":"The complexity of first-order and monadic second-order logic revisited. Annals of pure and applied logic, 130(1--3):3--31","author":"Frick Markus","year":"2004","unstructured":"Markus Frick and Martin Grohe . The complexity of first-order and monadic second-order logic revisited. Annals of pure and applied logic, 130(1--3):3--31 , 2004 . Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Annals of pure and applied logic, 130(1--3):3--31, 2004."},{"key":"e_1_3_2_2_24_1","volume-title":"Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Methods Comput. Sci., 11(1)","author":"Gajarsk\u00fd Jakub","year":"2015","unstructured":"Jakub Gajarsk\u00fd and Petr Hlinen\u00fd . Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Methods Comput. Sci., 11(1) , 2015 . Jakub Gajarsk\u00fd and Petr Hlinen\u00fd. Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Methods Comput. Sci., 11(1), 2015."},{"issue":"1","key":"e_1_3_2_2_25_1","first-page":"1","article-title":"Locally checkable proofs in distributed computing","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","unstructured":"Mika G\u00f6\u00f6s and Jukka Suomela . Locally checkable proofs in distributed computing . Theory Comput. , 12 ( 1 ): 1 -- 33 , 2016 . Mika G\u00f6\u00f6s and Jukka Suomela. Locally checkable proofs in distributed computing. Theory Comput., 12(1):1--33, 2016.","journal-title":"Theory Comput."},{"key":"e_1_3_2_2_26_1","volume-title":"Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 64(3):1--32","author":"Grohe Martin","year":"2017","unstructured":"Martin Grohe , Stephan Kreutzer , and Sebastian Siebertz . Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 64(3):1--32 , 2017 . Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 64(3):1--32, 2017."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_57"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_3_2_2_32_1","first-page":"115","volume-title":"Bounded Height Trees and Tree-Depth","author":"Nesetril Jaroslav","year":"2012","unstructured":"Jaroslav Nesetril and Patrice Ossona de Mendez . Bounded Height Trees and Tree-Depth , pages 115 -- 144 . Springer , 2012 . Jaroslav Nesetril and Patrice Ossona de Mendez. Bounded Height Trees and Tree-Depth, pages 115--144. Springer, 2012."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.37236\/3367"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.27"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56610-4_89"},{"issue":"1","key":"e_1_3_2_2_38_1","first-page":"103","article-title":"Finite automata and the logic of one-place predicates","volume":"3","author":"Trakhtenbrot Boris Avraamovich","year":"1962","unstructured":"Boris Avraamovich Trakhtenbrot . Finite automata and the logic of one-place predicates . Sibirskii Matematicheskii Zhurnal , 3 ( 1 ): 103 -- 131 , 1962 . Boris Avraamovich Trakhtenbrot. Finite automata and the logic of one-place predicates. Sibirskii Matematicheskii Zhurnal, 3(1):103--131, 1962.","journal-title":"Sibirskii Matematicheskii Zhurnal"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","location":"Salerno Italy","acronym":"PODC '22","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538416","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":38,"alternative-id":["10.1145\/3519270.3538416","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538416","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}