{"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":1781078173414,"version":"3.54.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,5]],"date-time":"2020-07-05T00:00:00Z","timestamp":1593907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme ERC Synergy Grant DYNASNET","award":["810115"],"award-info":[{"award-number":["810115"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme (Marie Sk\u0142odowska-Curie","award":["665778"],"award-info":[{"award-number":["665778"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme ERC Consolidator Grant DISTRUCT","award":["648527"],"award-info":[{"award-number":["648527"]}]},{"name":"GA\u010cR, European Associated Laboratory","award":["CE-ITI P202\/12\/G061"],"award-info":[{"award-number":["CE-ITI P202\/12\/G061"]}]},{"name":"NCN","award":["2016\/21\/D\/ST6\/01485"],"award-info":[{"award-number":["2016\/21\/D\/ST6\/01485"]}]},{"name":"European Research Council"},{"name":"National Science Centre of Poland (NCN) via POLONEZ","award":["UMO-2015\/19\/P\/ST6\/03998"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with\n            <jats:italic>structurally bounded expansion<\/jats:italic>\n            , defined as first-order transductions of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth covers (or colorings), replacing treedepth by its dense analogue called shrubdepth.\n          <\/jats:p>","DOI":"10.1145\/3382093","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T04:04:52Z","timestamp":1594008292000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["First-Order Interpretations of Bounded Expansion Classes"],"prefix":"10.1145","volume":"21","author":[{"given":"Jakub","family":"Gajarsk\u00fd","sequence":"first","affiliation":[{"name":"Technical University Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[{"name":"Technical University Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaroslav","family":"Ne\u0161ET\u0159il","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrice Ossona De","family":"Mendez","sequence":"additional","affiliation":[{"name":"CAMS (CNRS, UMR 8557), Paris, France, and Charles University, Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Szymon","family":"Toru\u0144czyk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Scandinavian Workshop on Algorithm\u00a0Theory. Springer, 142--152","author":"Atminas A.","unstructured":"A. Atminas , V. V. Lozin , and I. Razgon . 2012. Linear time algorithm for computing a small biclique in graphs without long induced paths . In Scandinavian Workshop on Algorithm\u00a0Theory. Springer, 142--152 . A. Atminas, V. V. Lozin, and I. Razgon. 2012. Linear time algorithm for computing a small biclique in graphs without long induced paths. In Scandinavian Workshop on Algorithm\u00a0Theory. Springer, 142--152."},{"key":"#cr-split#-e_1_2_1_2_1.1","doi-asserted-by":"crossref","unstructured":"A. Blumensath and B. Courcelle. 2010. On the Monadic second-order transduction hierarchy. Logical Methods in Computer Science 6 2 (2010). DOI:https:\/\/doi.org\/10.2168\/LMCS-6(2:2)2010 10.2168\/LMCS-6(2:2)2010","DOI":"10.2168\/LMCS-6(2:2)2010"},{"key":"#cr-split#-e_1_2_1_2_1.2","doi-asserted-by":"crossref","unstructured":"A. Blumensath and B. Courcelle. 2010. On the Monadic second-order transduction hierarchy. Logical Methods in Computer Science 6 2 (2010). DOI:https:\/\/doi.org\/10.2168\/LMCS-6(2:2)2010","DOI":"10.2168\/LMCS-6(2:2)2010"},{"key":"e_1_2_1_3_1","first-page":"142","article-title":"Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science. Vol. 2. Elsevier, Amsterdam","volume":"5","author":"Courcelle B.","year":"1990","unstructured":"B. Courcelle . 1990 . Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science. Vol. 2. Elsevier, Amsterdam , Chapter 5 , 142 -- 193 . B. Courcelle. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science. Vol. 2. Elsevier, Amsterdam, Chapter 5, 142--193.","journal-title":"Chapter"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90148-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.021"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"B. Courcelle and J. Engelfriet. 2012. Graph Structure and Monadic Second-order Logic: A Language-theoretic Approach. Vol. 138. Cambridge University Press.  B. Courcelle and J. Engelfriet. 2012. Graph Structure and Monadic Second-order Logic: A Language-theoretic Approach. Vol. 138. Cambridge University Press.","DOI":"10.1017\/CBO9780511977619"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_2_1_9_1","volume-title":"22nd Annual IEEE Symposium on Logic in Computer Science. 270--279","author":"Dawar A.","unstructured":"A. Dawar , M. Grohe , and S. Kreutzer . 2007. Locally excluding a minor . In 22nd Annual IEEE Symposium on Logic in Computer Science. 270--279 . A. Dawar, M. Grohe, and S. Kreutzer. 2007. Locally excluding a minor. In 22nd Annual IEEE Symposium on Logic in Computer Science. 270--279."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276923"},{"key":"e_1_2_1_11_1","volume-title":"33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, 121--131","author":"Durand A.","unstructured":"A. Durand , N. Schweikardt , and L. Segoufin . 2014. Enumerating answers to first-order queries over databases of low degree . In 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, 121--131 . A. Durand, N. Schweikardt, and L. Segoufin. 2014. Enumerating answers to first-order queries over databases of low degree. In 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, 121--131."},{"key":"e_1_2_1_12_1","volume-title":"51st Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Dvo\u0159\u00e1k Z.","year":"2010","unstructured":"Z. Dvo\u0159\u00e1k , D. Kr\u00e1\u013e , and R. Thomas . 2010. Deciding first-order properties for sparse graphs . In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201910) . 133--142. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2010 .20 10.1109\/FOCS.2010.20 Z. Dvo\u0159\u00e1k, D. Kr\u00e1\u013e, and R. Thomas. 2010. Deciding first-order properties for sparse graphs. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201910). 133--142. DOI:https:\/\/doi.org\/10.1109\/FOCS.2010.20"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_2_1_14_1","volume-title":"21st International Symposium on Fundamentals of Computation Theory, (FCT\u201917)","author":"Eickmeyer K.","unstructured":"K. Eickmeyer and K. Kawarabayashi . 2017. FO model checking on map graphs . In 21st International Symposium on Fundamentals of Computation Theory, (FCT\u201917) . 204--216. K. Eickmeyer and K. Kawarabayashi. 2017. FO model checking on map graphs. In 21st International Symposium on Fundamentals of Computation Theory, (FCT\u201917). 204--216."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_2_1_17_1","volume-title":"56th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Gajarsk\u00fd J.","year":"2015","unstructured":"J. Gajarsk\u00fd , P. Hlin\u011bn\u00fd , D. Lokshtanov , J. Obdr\u017e\u00e1lek , S. Ordyniak , M. S. Ramanujan , and S. Saurabh . 2015. FO model checking on posets of bounded width . In 56th Annual Symposium on Foundations of Computer Science (FOCS) , 2015 . IEEE, 963--974. J. Gajarsk\u00fd, P. Hlin\u011bn\u00fd, D. Lokshtanov, J. Obdr\u017e\u00e1lek, S. Ordyniak, M. S. Ramanujan, and S. Saurabh. 2015. FO model checking on posets of bounded width. In 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015. IEEE, 963--974."},{"key":"e_1_2_1_18_1","volume-title":"31st Annual ACM\/IEEE Symposium on Logic in Computer Science. ACM, 176--184","author":"Gajarsk\u00fd J.","unstructured":"J. Gajarsk\u00fd , P. Hlin\u011bn\u00fd , J. Obdr\u017e\u00e1lek , D. Lokshtanov , and M. S. Ramanujan . 2016. A new perspective on FO model checking of dense graph classes . In 31st Annual ACM\/IEEE Symposium on Logic in Computer Science. ACM, 176--184 . J. Gajarsk\u00fd, P. Hlin\u011bn\u00fd, J. Obdr\u017e\u00e1lek, D. Lokshtanov, and M. S. Ramanujan. 2016. A new perspective on FO model checking of dense graph classes. In 31st Annual ACM\/IEEE Symposium on Logic in Computer Science. ACM, 176--184."},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"First-order interpretations of bounded expansion classes. In 45th International Colloquium on Automata, Languages, and Programming","volume":"126","author":"Gajarsk\u00fd J.","year":"2018","unstructured":"J. Gajarsk\u00fd , S. Kreutzer , J. Ne\u0161et\u0159il , P. Ossona de Mendez , M. Pilipczuk , S. Siebertz , and S. Toru\u0144czyk . 2018 . First-order interpretations of bounded expansion classes. In 45th International Colloquium on Automata, Languages, and Programming , ICALP. 126 : 1 -- 126 :14. J. Gajarsk\u00fd, S. Kreutzer, J. Ne\u0161et\u0159il, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toru\u0144czyk. 2018. First-order interpretations of bounded expansion classes. In 45th International Colloquium on Automata, Languages, and Programming, ICALP. 126:1--126:14.","journal-title":"ICALP."},{"key":"e_1_2_1_20_1","volume-title":"Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science 15, 1","author":"Ganian R.","year":"2019","unstructured":"R. Ganian , P. Hlin\u011bn\u00fd , J. Ne\u0161et\u0159il , J. Obdr\u017e\u00e1lek , and P. Ossona de Mendez . 2019 . Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science 15, 1 (2019). https:\/\/lmcs.episciences.org\/5149. R. Ganian, P. Hlin\u011bn\u00fd, J. Ne\u0161et\u0159il, J. Obdr\u017e\u00e1lek, and P. Ossona de Mendez. 2019. Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science 15, 1 (2019). https:\/\/lmcs.episciences.org\/5149."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"R. Ganian P. Hlin\u011bn\u00fd J. Obdr\u017e\u00e1lek J. Schwartz J. Teska and D. Kr\u00e1\u013e. 2013. FO model checking of interval graphs. In International Colloquium on Automata Languages and Programming. Springer 250--262.  R. Ganian P. Hlin\u011bn\u00fd J. Obdr\u017e\u00e1lek J. Schwartz J. Teska and D. Kr\u00e1\u013e. 2013. FO model checking of interval graphs. In International Colloquium on Automata Languages and Programming. Springer 250--262.","DOI":"10.1007\/978-3-642-39212-2_24"},{"key":"e_1_2_1_22_1","volume-title":"MFCS 2012 (Lecture Notes in Computer Science)","volume":"7464","author":"Ganian R.","unstructured":"R. Ganian , P. Hlin\u011bn\u00fd , J. Ne\u0161et\u0159il , J. Obdr\u017e\u00e1lek , P. Ossona de Mendez, and R. Ramadurai. 2012. When trees grow low: Shrubs and fast MSO1 . In MFCS 2012 (Lecture Notes in Computer Science) , Vol. 7464 . Springer-Verlag, 419--430. R. Ganian, P. Hlin\u011bn\u00fd, J. Ne\u0161et\u0159il, J. Obdr\u017e\u00e1lek, P. Ossona de Mendez, and R. Ramadurai. 2012. When trees grow low: Shrubs and fast MSO1. In MFCS 2012 (Lecture Notes in Computer Science), Vol. 7464. Springer-Verlag, 419--430."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1996.0519"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. Grohe and S. Kreutzer. 2011. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics (Contemporary mathematics). 181--206.  M. Grohe and S. Kreutzer. 2011. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics (Contemporary mathematics). 181--206.","DOI":"10.1090\/conm\/558\/11051"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_2_1_27_1","volume-title":"WG 2000 (Lecture Notes in Computer Science)","volume":"1928","author":"Gurski F.","unstructured":"F. Gurski and E. Wanke . 2000. The tree-width of clique-width bounded graphs without Kn, n . In WG 2000 (Lecture Notes in Computer Science) , Vol. 1928 . Springer, 196--205. F. Gurski and E. Wanke. 2000. The tree-width of clique-width bounded graphs without Kn, n. In WG 2000 (Lecture Notes in Computer Science), Vol. 1928. Springer, 196--205."},{"key":"e_1_2_1_28_1","volume-title":"12th International Symposium on Parameterized and Exact Computation (IPEC\u201917)","author":"Hlinen\u00fd P.","unstructured":"P. Hlinen\u00fd , F. Pokr\u00fdvka , and B. Roy . 2017. FO model checking of geometric graphs . In 12th International Symposium on Parameterized and Exact Computation (IPEC\u201917) . 19:1--19:12. P. Hlinen\u00fd, F. Pokr\u00fdvka, and B. Roy. 2017. FO model checking of geometric graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC\u201917). 19:1--19:12."},{"key":"e_1_2_1_29_1","volume-title":"16th International Conference on Database Theory. 10--20","author":"Kazana W.","unstructured":"W. Kazana and L. Segoufin . 2013. Enumeration of first-order queries on classes of structures with bounded expansion . In 16th International Conference on Database Theory. 10--20 . W. Kazana and L. Segoufin. 2013. Enumeration of first-order queries on classes of structures with bounded expansion. In 16th International Conference on Database Theory. 10--20."},{"key":"e_1_2_1_30_1","volume-title":"32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, 297--308","author":"Kazana W.","unstructured":"W. Kazana and L. Segoufin . 2013. Enumeration of first-order queries on classes of structures with bounded expansion . In 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, 297--308 . W. Kazana and L. Segoufin. 2013. Enumeration of first-order queries on classes of structures with bounded expansion. In 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, 297--308."},{"key":"e_1_2_1_31_1","volume-title":"43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201917)","author":"Kwon O.","unstructured":"O. Kwon , Mi. Pilipczuk , and S. Siebertz . 2017. On low rank-width colorings . In 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201917) . 372--385. O. Kwon, Mi. Pilipczuk, and S. Siebertz. 2017. On low rank-width colorings. In 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201917). 372--385."},{"key":"#cr-split#-e_1_2_1_32_1.1","doi-asserted-by":"crossref","unstructured":"C. L\u00f6ding. 2012. Basics on tree automata. In Modern Applications of Automata Theory. 79--110. DOI:https:\/\/doi.org\/10.1142\/9789814271059_0003 10.1142\/9789814271059_0003","DOI":"10.1142\/9789814271059_0003"},{"key":"#cr-split#-e_1_2_1_32_1.2","doi-asserted-by":"crossref","unstructured":"C. L\u00f6ding. 2012. Basics on tree automata. In Modern Applications of Automata Theory. 79--110. DOI:https:\/\/doi.org\/10.1142\/9789814271059_0003","DOI":"10.1142\/9789814271059_0003"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"e_1_2_1_36_1","volume-title":"Algorithms and Combinatorics","author":"Ne\u0161et\u0159il J.","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez . 2012. Sparsity (Graphs, Structures, and Algorithms). Algorithms and Combinatorics , Vol. 28 . Springer . 465 pages. J. Ne\u0161et\u0159il and P. Ossona de Mendez. 2012. Sparsity (Graphs, Structures, and Algorithms). Algorithms and Combinatorics, Vol. 28. Springer. 465 pages."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435385"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"L. Segoufin and W. Kazana. 2011. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science 7 (2011).  L. Segoufin and W. Kazana. 2011. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science 7 (2011).","DOI":"10.2168\/LMCS-7(2:20)2011"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382093","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:08Z","timestamp":1750197728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,5]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3382093"],"URL":"https:\/\/doi.org\/10.1145\/3382093","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,5]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}