{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:03:04Z","timestamp":1750492984167,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE92-0027"],"award-info":[{"award-number":["ANR-20-CE92-0027"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG 446200270"],"award-info":[{"award-number":["DFG 446200270"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["948057"],"award-info":[{"award-number":["948057"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,8]]},"DOI":"10.1145\/3661814.3662089","type":"proceedings-article","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T12:30:12Z","timestamp":1718973012000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1740-7478","authenticated-orcid":false,"given":"Nicole","family":"Schirrmacher","sequence":"first","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-1198","authenticated-orcid":false,"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4175-7793","authenticated-orcid":false,"given":"Giannos","family":"Stamoulis","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Informatics, and Mechanics, Institute of Informatics, University of Warsaw, Poland, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0470-1800","authenticated-orcid":false,"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[{"name":"LIRMM, Universit\u00e9 de Montpellier, CNRS, Montpellier, France, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4298-8876","authenticated-orcid":false,"given":"Alexandre","family":"Vigny","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Clermont Auvergne, Clermont-Ferrand, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232056"},{"key":"e_1_3_2_1_3_1","volume-title":"Separator logic and star-free expressions for graphs. arXiv preprint arXiv:2107.13953","author":"Boja\u0144czyk Miko\u0142aj","year":"2021","unstructured":"Miko\u0142aj Boja\u0144czyk. 2021. Separator logic and star-free expressions for graphs. arXiv preprint arXiv:2107.13953 (2021)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520037"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3486655"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90064-Z"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/140988553"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_2_1_11_1","volume-title":"First-Order Model Checking on Monadically Stable Graph Classes. arXiv preprint arXiv:2311.18740","author":"Dreier Jan","year":"2023","unstructured":"Jan Dreier, Ioannis Eleftheriadis, Nikolas M\u00e4hlmann, Rose McCarty, Micha\u0142 Pilipczuk, and Szymon Toru\u0144czyk. 2023. First-Order Model Checking on Monadically Stable Graph Classes. arXiv preprint arXiv:2311.18740 (2023)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585186"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.104"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.20"},{"volume-title":"Finite model theory","author":"Ebbinghaus Heinz-Dieter","key":"e_1_3_2_1_15_1","unstructured":"Heinz-Dieter Ebbinghaus and J\u00f6rg Flum. 1999. Finite model theory. Springer Science & Business Media."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55751-8_17"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_3_2_1_18_1","volume-title":"Thilikos","author":"Fomin Fedor V.","year":"2023","unstructured":"Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. 2023. Compound Logics for Modification Problems. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 261). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 61:1--61:21."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384318"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 30th EACSL Annual Conference on Computer Science Logic (CSL) (LIPIcs","volume":"18","author":"Gajarsk\u00fd Jakub","year":"2022","unstructured":"Jakub Gajarsk\u00fd, Maximilian Gorsky, and Stephan Kreutzer. 2022. Differential Games, Locality, and Model Checking for FO Logic of Graphs. In Proceedings of the 30th EACSL Annual Conference on Computer Science Logic (CSL) (LIPIcs, Vol. 216). 22:1--22:18."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_24"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.005"},{"key":"e_1_3_2_1_25_1","volume-title":"Thilikos","author":"Golovach Petr A.","year":"2022","unstructured":"Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. 2022. Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. arXiv preprint arXiv:2211.01723 (2022)."},{"key":"e_1_3_2_1_26_1","volume-title":"Thilikos","author":"Golovach Petr A.","year":"2023","unstructured":"Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. 2023. Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 3684--3699."},{"volume-title":"Finite Model Theory and its applications","author":"Gr\u00e4del Erich","key":"e_1_3_2_1_27_1","unstructured":"Erich Gr\u00e4del, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y Vardi, Yde Venema, and Scott Weinstein. 2007. Finite Model Theory and its applications. Springer."},{"volume-title":"Automata, logics, and infinite games: a guide to current research","author":"Gr\u00e4del Erich","key":"e_1_3_2_1_28_1","unstructured":"Erich Gr\u00e4del, Wolfgang Thomas, and Thomas Wilke. 2003. Automata, logics, and infinite games: a guide to current research. Vol. 2500. Springer."},{"key":"e_1_3_2_1_29_1","volume-title":"Logic, graphs, and algorithms. Logic and automata 2","author":"Grohe Martin","year":"2008","unstructured":"Martin Grohe. 2008. Logic, graphs, and algorithms. Logic and automata 2 (2008), 357--422."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993700"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196970"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC) (LIPIcs","volume":"12","author":"Hlinen\u00fd Petr","year":"2017","unstructured":"Petr Hlinen\u00fd, Filip Pokr\u00fdvka, and Bodhayan Roy. 2017. FO Model Checking of Geometric Graphs. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC) (LIPIcs, Vol. 89). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1--19:12."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005133"},{"key":"e_1_3_2_1_36_1","first-page":"1","article-title":"Gaifman normal forms for counting extensions of first-order logic. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 107)","volume":"133","author":"Kuske Dietrich","year":"2018","unstructured":"Dietrich Kuske and Nicole Schweikardt. 2018. Gaifman normal forms for counting extensions of first-order logic. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 133:1--133:14.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"volume-title":"Elements of finite model theory","author":"Libkin Leonid","key":"e_1_3_2_1_37_1","unstructured":"Leonid Libkin. 2004. Elements of finite model theory. Vol. 41. Springer."},{"key":"e_1_3_2_1_38_1","first-page":"1","article-title":"Reducing CMSO Model Checking to Highly Connected Graphs. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 107)","volume":"135","author":"Lokshtanov Daniel","year":"2018","unstructured":"Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. 2018. Reducing CMSO Model Checking to Highly Connected Graphs. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 135:1--135:14.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_39_1","volume-title":"Patrice Ossona de Mendez, and Sebastian Siebertz","author":"Ne\u0161et\u0159il Jaroslav","year":"2023","unstructured":"Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, and Sebastian Siebertz. 2023. Modulo-counting first-order logic on bounded expansion classes. Discrete Mathematics (2023), 113700."},{"key":"e_1_3_2_1_40_1","first-page":"1","article-title":"Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP) (LIPIcs, Vol. 229)","volume":"102","author":"Pilipczuk Micha\u0142","year":"2022","unstructured":"Micha\u0142 Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toru\u0144czyk, and Alexandre Vigny. 2022. Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, (ICALP) (LIPIcs, Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 102:1--102:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3595922"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387660"}],"event":{"name":"LICS '24: 39th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE Computer Society","EACSL"],"location":"Tallinn Estonia","acronym":"LICS '24"},"container-title":["Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662089","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661814.3662089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:08Z","timestamp":1750290248000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":45,"alternative-id":["10.1145\/3661814.3662089","10.1145\/3661814"],"URL":"https:\/\/doi.org\/10.1145\/3661814.3662089","relation":{},"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}