{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:13Z","timestamp":1781078173428,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["444419611"],"award-info":[{"award-number":["444419611"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585186","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"567-580","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["First-Order Model Checking on Structurally Sparse Graph Classes"],"prefix":"10.1145","author":[{"given":"Jan","family":"Dreier","sequence":"first","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikolas","family":"M\u00e4hlmann","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Logic and Structure Workshop in Warwick \u2013 Open Problem Session. https:\/\/warwick.ac.uk\/fac\/sci\/maths\/people\/staff\/daniel_kral\/alglogstr\/openproblems.pdf [Online; accessed 07-Feb-2023]","unstructured":"2016. Algorithms , Logic and Structure Workshop in Warwick \u2013 Open Problem Session. https:\/\/warwick.ac.uk\/fac\/sci\/maths\/people\/staff\/daniel_kral\/alglogstr\/openproblems.pdf [Online; accessed 07-Feb-2023] 2016. Algorithms, Logic and Structure Workshop in Warwick \u2013 Open Problem Session. https:\/\/warwick.ac.uk\/fac\/sci\/maths\/people\/staff\/daniel_kral\/alglogstr\/openproblems.pdf [Online; accessed 07-Feb-2023]"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093870870"},{"key":"e_1_3_2_1_4_1","first-page":"1","article-title":"Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. In LICS \u201922","volume":"54","author":"Bonnet \u00c9douard","year":"2022","unstructured":"\u00c9douard Bonnet , Jan Dreier , Jakub Gajarsk\u00fd , Stephan Kreutzer , Nikolas M\u00e4hlmann , Pierre Simon , and Szymon Torunczyk . 2022 . Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. In LICS \u201922 . ACM , 54 : 1 \u2013 54 :13. \u00c9douard Bonnet, Jan Dreier, Jakub Gajarsk\u00fd, Stephan Kreutzer, Nikolas M\u00e4hlmann, Pierre Simon, and Szymon Torunczyk. 2022. Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. In LICS \u201922. ACM, 54:1\u201354:13.","journal-title":"ACM"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520037"},{"key":"e_1_3_2_1_6_1","first-page":"1","article-title":"Twin-width I: tractable FO model checking","volume":"69","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet , Eun Jung Kim , St\u00e9phan Thomass\u00e9 , and R\u00e9mi Watrigant . 2021 . Twin-width I: tractable FO model checking . ACM Journal of the ACM (JACM) , 69 , 1 (2021), 1 \u2013 46 . \u00c9douard Bonnet, Eun Jung Kim, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2021. Twin-width I: tractable FO model checking. ACM Journal of the ACM (JACM), 69, 1 (2021), 1\u201346.","journal-title":"ACM Journal of the ACM (JACM)"},{"key":"e_1_3_2_1_7_1","unstructured":"Samuel Braunfeld and Michael C Laskowski. 2022. Existential characterizations of monadic NIP. arXiv preprint arXiv:2209.05120. \t\t\t\t  Samuel Braunfeld and Michael C Laskowski. 2022. Existential characterizations of monadic NIP. arXiv preprint arXiv:2209.05120."},{"key":"e_1_3_2_1_8_1","volume-title":"The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Information and computation, 85, 1","author":"Courcelle Bruno","year":"1990","unstructured":"Bruno Courcelle . 1990. The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Information and computation, 85, 1 ( 1990 ), 12\u201375. Bruno Courcelle. 1990. The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Information and computation, 85, 1 (1990), 12\u201375."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533349"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Jan Dreier Nikolas M\u00e4hlmann and Sebastian Siebertz. 2023. First-Order Model Checking on Structurally Sparse Graph Classes. arXiv preprint arXiv:2302.03527. \t\t\t\t  Jan Dreier Nikolas M\u00e4hlmann and Sebastian Siebertz. 2023. First-Order Model Checking on Structurally Sparse Graph Classes. arXiv preprint arXiv:2302.03527.","DOI":"10.1145\/3564246.3585186"},{"key":"e_1_3_2_1_13_1","unstructured":"Jan Dreier Nikolas M\u00e4hlmann Sebastian Siebertz and Szymon Toru\u0144czyk. [n. d.]. Nowhere Dense Model Checking Revisited. forthcoming \t\t\t\t  Jan Dreier Nikolas M\u00e4hlmann Sebastian Siebertz and Szymon Toru\u0144czyk. [n. d.]. Nowhere Dense Model Checking Revisited. forthcoming"},{"key":"e_1_3_2_1_14_1","unstructured":"Jan Dreier Nikolas M\u00e4hlmann Sebastian Siebertz and Szymon Toru\u0144czyk. 2022. Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes. arXiv preprint arXiv:2206.13765v1. \t\t\t\t  Jan Dreier Nikolas M\u00e4hlmann Sebastian Siebertz and Szymon Toru\u0144czyk. 2022. Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes. arXiv preprint arXiv:2206.13765v1."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.20"},{"key":"e_1_3_2_1_16_1","volume-title":"Finite model theory","author":"Ebbinghaus Heinz-Dieter","unstructured":"Heinz-Dieter Ebbinghaus and J\u00f6rg Flum . 1999. Finite model theory . Springer Science & Business Media . Heinz-Dieter Ebbinghaus and J\u00f6rg Flum. 1999. Finite model theory. Springer Science & Business Media."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55751-8_17"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_1_20_1","volume-title":"Studies in Logic and the Foundations of Mathematics. 107","author":"Gaifman Haim","unstructured":"Haim Gaifman . 1982. On local and non-local properties . In Studies in Logic and the Foundations of Mathematics. 107 , Elsevier , 105\u2013135. Haim Gaifman. 1982. On local and non-local properties. In Studies in Logic and the Foundations of Mathematics. 107, Elsevier, 105\u2013135."},{"key":"e_1_3_2_1_21_1","unstructured":"Jakub Gajarsk\u1ef3 Maximilian Gorsky and Stephan Kreutzer. 2020. Differential games locality and model checking for FO logic of graphs. arXiv preprint arXiv:2007.11345. \t\t\t\t  Jakub Gajarsk\u1ef3 Maximilian Gorsky and Stephan Kreutzer. 2020. Differential games locality and model checking for FO logic of graphs. arXiv preprint arXiv:2007.11345."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3383206"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_3_2_1_24_1","volume-title":"Marek Soko\u0142 owski, and Szymon Toru\u0144czyk","author":"Gajarsk\u00fd Jakub","year":"2023","unstructured":"Jakub Gajarsk\u00fd , Nikolas M\u00e4hlmann , Rose McCarty , Pierre Ohlmann , Micha\u0142 Pilipczuk , Wojciech Przybyszewski , Sebastian Siebertz , Marek Soko\u0142 owski, and Szymon Toru\u0144czyk . 2023 . Flipper games for monadically stable graph classes. arXiv preprint arXiv:2301.13735v1. Jakub Gajarsk\u00fd, Nikolas M\u00e4hlmann, Rose McCarty, Pierre Ohlmann, Micha\u0142 Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Soko\u0142 owski, and Szymon Toru\u0144czyk. 2023. Flipper games for monadically stable graph classes. arXiv preprint arXiv:2301.13735v1."},{"key":"e_1_3_2_1_25_1","first-page":"1868","volume-title":"49th International Colloquium on Automata, Languages, and Programming. 123:1\u2013123:21","author":"Gajarsk\u00fd Jakub","year":"2022","unstructured":"Jakub Gajarsk\u00fd , Micha\u0142 Pilipczuk , Wojciech Przybyszewski , and Szymon Toru\u0144czyk . 2022 . Twin-Width and Types. In 49th International Colloquium on Automata, Languages, and Programming. 123:1\u2013123:21 . isbn:978-3-95977-235-8 issn: 1868 - 8969 Jakub Gajarsk\u00fd, Micha\u0142 Pilipczuk, Wojciech Przybyszewski, and Szymon Toru\u0144czyk. 2022. Twin-Width and Types. In 49th International Colloquium on Automata, Languages, and Programming. 123:1\u2013123:21. isbn:978-3-95977-235-8 issn:1868-8969"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533356"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Robert Ganian Petr Hlin\u011bn\u1ef3 Daniel Kr\u00e1l Jan Obdr\u017e\u00e1lek Jarett Schwartz and Jakub Teska. 2013. FO model checking of interval graphs. In International Colloquium on Automata Languages and Programming. 250\u2013262. \t\t\t\t  Robert Ganian Petr Hlin\u011bn\u1ef3 Daniel Kr\u00e1l Jan Obdr\u017e\u00e1lek Jarett Schwartz and Jakub Teska. 2013. FO model checking of interval graphs. In International Colloquium on Automata Languages and Programming. 250\u2013262.","DOI":"10.1007\/978-3-642-39212-2_24"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.005"},{"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\u2013422. Martin Grohe. 2008. Logic, graphs, and algorithms.. Logic and automata, 2 (2008), 357\u2013422."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11051"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1168753"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_2_1_33_1","volume-title":"FO Model Checking of Geometric Graphs. In 12th International Symposium on Parameterized and Exact Computation, IPEC","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 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Daniel Lokshtanov and Naomi Nishimura (Eds.) (LIPIcs , Vol. 89). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319: 12 . Petr Hlinen\u00fd, Filip Pokr\u00fdvka, and Bodhayan Roy. 2017. FO Model Checking of Geometric Graphs. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Daniel Lokshtanov and Naomi Nishimura (Eds.) (LIPIcs, Vol. 89). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319:12."},{"key":"e_1_3_2_1_34_1","volume-title":"A Shorter Model Theory","author":"Hodges Wilfrid","unstructured":"Wilfrid Hodges . 1997. A Shorter Model Theory . Cambridge University Press . Wilfrid Hodges. 1997. A Shorter Model Theory. Cambridge University Press."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_37_1","volume-title":"Algorithmic meta-theorems.. Finite and algorithmic model theory, 379","author":"Kreutzer Stephan","year":"2011","unstructured":"Stephan Kreutzer . 2011. Algorithmic meta-theorems.. Finite and algorithmic model theory, 379 ( 2011 ), 177\u2013270. Stephan Kreutzer. 2011. Algorithmic meta-theorems.. Finite and algorithmic model theory, 379 (2011), 177\u2013270."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_3_2_1_39_1","volume-title":"Interference in Cellular Networks: The Minimum Membership Set Cover Problem","author":"Kuhn Fabian","year":"1806","unstructured":"Fabian Kuhn , Pascal von Rickenbach , Roger Wattenhofer , Emo Welzl , and Aaron Zollinger . 2005. Interference in Cellular Networks: The Minimum Membership Set Cover Problem . In Computing and Combinatorics, Lusheng Wang (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg . 188\u2013198. isbn:978-3-540-3 1806 -4 Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, and Aaron Zollinger. 2005. Interference in Cellular Networks: The Minimum Membership Set Cover Problem. In Computing and Combinatorics, Lusheng Wang (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 188\u2013198. isbn:978-3-540-31806-4"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM9688"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM. \t\t\t\t  David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-100-2-101-107"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_2_1_44_1","volume-title":"Classification theory: and the number of non-isomorphic models","author":"Shelah Saharon","unstructured":"Saharon Shelah . 1990. Classification theory: and the number of non-isomorphic models . Elsevier . Saharon Shelah. 1990. Classification theory: and the number of non-isomorphic models. Elsevier."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_46_1","unstructured":"Szymon Toru\u0144czyk. 2022. Lectures on Finite Model Theory. \t\t\t\t  Szymon Toru\u0144czyk. 2022. Lectures on Finite Model Theory."},{"key":"e_1_3_2_1_47_1","volume-title":"30th annual symposium on foundations of computer science. 332\u2013337.","author":"Vaidya Pravin M","unstructured":"Pravin M Vaidya . 1989. Speeding-up linear programming using fast matrix multiplication . In 30th annual symposium on foundations of computer science. 332\u2013337. Pravin M Vaidya. 1989. Speeding-up linear programming using fast matrix multiplication. In 30th annual symposium on foundations of computer science. 332\u2013337."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":47,"alternative-id":["10.1145\/3564246.3585186","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585186","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}