{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T13:23:27Z","timestamp":1789997007751,"version":"4.0.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,5,31]],"date-time":"2014-05-31T00:00:00Z","timestamp":1401494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,5,31]]},"DOI":"10.1145\/2591796.2591851","type":"proceedings-article","created":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T08:01:58Z","timestamp":1443686518000},"page":"89-98","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Deciding first-order properties of nowhere dense graphs"],"prefix":"10.1145","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[{"name":"Technical University Berlin"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"Technical University Berlin"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248381"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281112"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/114891.114896"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00221-3"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.13"},{"key":"e_1_3_2_2_9_1","first-page":"157","volume-title":"Foundations of software technology and theoretical computer science (FSTTCS)","author":"Dawar A.","year":"2009","unstructured":"A. Dawar and S. Kreutzer . Domination problems in nowhere-dense classes of graphs . In Foundations of software technology and theoretical computer science (FSTTCS) , pages 157 -- 168 , 2009 . A. Dawar and S. Kreutzer. Domination problems in nowhere-dense classes of graphs. In Foundations of software technology and theoretical computer science (FSTTCS), pages 157--168, 2009."},{"key":"e_1_3_2_2_10_1","volume-title":"Graph Theory","author":"Diestel R.","year":"2005","unstructured":"R. Diestel . Graph Theory . Springer-Verlag , 3 rd edition, 2005 . R. Diestel. Graph Theory. Springer-Verlag, 3rd edition, 2005.","edition":"3"},{"key":"e_1_3_2_2_11_1","unstructured":"R.\n      Downey M.\n      Fellows and \n      U.\n      Taylor\n  . \n  The parameterized complexity of relational database queries and an improved characterization of W{1}\n  . In D. Bridges C. Calude P. Gibbons S. Reeves and I. Witten editors Combinatorics Complexity and Logic volume \n  39\n   of \n  Proceedings of DMTCS pages \n  194\n  --\n  213\n  . \n  Springer-Verlag 1996\n  .  R. Downey M. Fellows and U. Taylor. The parameterized complexity of relational database queries and an improved characterization of W{1}. In D. Bridges C. Calude P. Gibbons S. Reeves and I. Witten editors Combinatorics Complexity and Logic volume 39 of Proceedings of DMTCS pages 194--213. Springer-Verlag 1996."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.20"},{"key":"e_1_3_2_2_14_1","volume-title":"Finite Model Theory","author":"Ebbinghaus H.-D.","year":"1999","unstructured":"H.-D. Ebbinghaus and J. Flum . Finite Model Theory . Springer Verlag , 2 nd edition, 1999 . H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer Verlag, 2nd edition, 1999.","edition":"2"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_2_18_1","first-page":"105","volume-title":"Herbrand Symposium, Logic Colloquium '81","author":"Gaifman H.","year":"1982","unstructured":"H. Gaifman . On local and non-local properties. In J. Stern, editor , Herbrand Symposium, Logic Colloquium '81 , pages 105 -- 135 . North Holland , 1982 . H. Gaifman. On local and non-local properties. In J. Stern, editor, Herbrand Symposium, Logic Colloquium '81, pages 105--135. North Holland, 1982."},{"key":"e_1_3_2_2_19_1","series-title":"Texts in Logic and Games","first-page":"357","volume-title":"Logic and Automata -- History and Perspectives","author":"Grohe M.","year":"2007","unstructured":"M. Grohe . Logic, graphs, and algorithms . In J. Flum, E. Gr\u00e4del, and T. Wilke, editors, Logic and Automata -- History and Perspectives , volume 2 of Texts in Logic and Games , pages 357 -- 422 . Amsterdam University Press , 2007 . M. Grohe. Logic, graphs, and algorithms. In J. Flum, E. Gr\u00e4del, and T. Wilke, editors, Logic and Automata -- History and Perspectives, volume 2 of Texts in Logic and Games, pages 357--422. Amsterdam University Press, 2007."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627847"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11051"},{"key":"e_1_3_2_2_22_1","first-page":"21","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013","author":"Grohe M.","year":"2013","unstructured":"M. Grohe , S. Kreutzer , and S. Siebertz . Characterisations of nowhere dense graphs . In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013 ), pages 21 -- 40 , 2013 . M. Grohe, S. Kreutzer, and S. Siebertz. Characterisations of nowhere dense graphs. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), pages 21--40, 2013."},{"key":"e_1_3_2_2_23_1","volume-title":"Deciding first-order properties of nowhere dense graphs. CoRR, abs\/1311.3899","author":"Grohe M.","year":"2013","unstructured":"M. Grohe , S. Kreutzer , and S. Siebertz . Deciding first-order properties of nowhere dense graphs. CoRR, abs\/1311.3899 , 2013 . M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. CoRR, abs\/1311.3899, 2013."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974960.006"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873631"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972924.5"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"crossref","unstructured":"J. Ne\u0161et\u0159il and P. O. de Mendez. Sparsity. Springer 2012.  J. Ne\u0161et\u0159il and P. O. de Mendez. Sparsity . Springer 2012.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_3_2_2_32_1","volume-title":"Grad and classes with bounded expansion ii. algorithmic aspects. arXiv, math\/0508324v2","author":"Ne\u0161et\u0159il J.","year":"2005","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez . Grad and classes with bounded expansion ii. algorithmic aspects. arXiv, math\/0508324v2 , 2005 . J. Ne\u0161et\u0159il and P. Ossona de Mendez. Grad and classes with bounded expansion ii. algorithmic aspects. arXiv, math\/0508324v2, 2005."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"event":{"name":"STOC '14: Symposium on Theory of Computing","location":"New York New York","acronym":"STOC '14","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591851","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591796.2591851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:55:45Z","timestamp":1750215345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":34,"alternative-id":["10.1145\/2591796.2591851","10.1145\/2591796"],"URL":"https:\/\/doi.org\/10.1145\/2591796.2591851","relation":{},"subject":[],"published":{"date-parts":[[2014,5,31]]},"assertion":[{"value":"2014-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}