{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:36:19Z","timestamp":1770071779260,"version":"3.49.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,9,10]],"date-time":"2016-09-10T00:00:00Z","timestamp":1473465600000},"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":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2016,11,15]]},"abstract":"<jats:p>\n            We study on which classes of graphs first-order logic (\n            <jats:sc>fo<\/jats:sc>\n            ) and monadic second-order logic (\n            <jats:sc>mso<\/jats:sc>\n            ) have the same expressive power. We show that for all classes C of graphs that are closed under taking subgraphs,\n            <jats:sc>fo<\/jats:sc>\n            and\n            <jats:sc>mso<\/jats:sc>\n            have the same expressive power on C if and only if, C has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking\n            <jats:italic>induced<\/jats:italic>\n            subgraphs, we show an analogous result for guarded second-order logic (\n            <jats:sc>gso<\/jats:sc>\n            ), the variant of\n            <jats:sc>mso<\/jats:sc>\n            that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman--Vaught-type theorem that works for infinite collections of structures despite being constructive.\n          <\/jats:p>","DOI":"10.1145\/2946799","type":"journal-article","created":{"date-parts":[[2016,9,12]],"date-time":"2016-09-12T13:33:37Z","timestamp":1473687217000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Where First-Order and Monadic Second-Order Logic Coincide"],"prefix":"10.1145","volume":"17","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[{"name":"Universit\u00e4t zu L\u00fcbeck, L\u00fcbeck, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"e_1_2_1_3_1","volume-title":"Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach. Encyclopedia of mathematics and its applications","author":"Courcelle Bruno","unstructured":"Bruno Courcelle and Joost Engelfriet . 2012. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach. Encyclopedia of mathematics and its applications , Vol. 138 . Cambridge University Press , Cambridge . Bruno Courcelle and Joost Engelfriet. 2012. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach. Encyclopedia of mathematics and its applications, Vol. 138. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1166"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","volume":"14","author":"Elberfeld Michael","year":"2012","unstructured":"Michael Elberfeld , Andreas Jakoby , and Till Tantau . 2012 . Algorithmic meta theorems for circuit classes of constant and logarithmic depth . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) (LIPIcs), Vol. 14 . Schloss Dagstuhl LZI, Dagstuhl, 66--77. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS. 2012.66 10.4230\/LIPIcs.STACS.2012.66 Michael Elberfeld, Andreas Jakoby, and Till Tantau. 2012. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) (LIPIcs), Vol. 14. Schloss Dagstuhl LZI, Dagstuhl, 66--77. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2012.66"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-47-1-57-103"},{"key":"e_1_2_1_8_1","volume-title":"Kernelizing MSO properties of trees of fixed height, and some consequences. Logical Methods in Computer Science 11, 1","author":"Gajarsk\u00fd Jakub","year":"2015","unstructured":"Jakub Gajarsk\u00fd and Petr Hlinen\u00fd . 2015. Kernelizing MSO properties of trees of fixed height, and some consequences. Logical Methods in Computer Science 11, 1 ( 2015 ). DOI:http:\/\/dx.doi.org\/10.2168\/LMCS-11(1:19)2015 10.2168\/LMCS-11(1:19)2015 Jakub Gajarsk\u00fd and Petr Hlinen\u00fd. 2015. Kernelizing MSO properties of trees of fixed height, and some consequences. Logical Methods in Computer Science 11, 1 (2015). DOI:http:\/\/dx.doi.org\/10.2168\/LMCS-11(1:19)2015"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90053-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/507382.507388"},{"key":"e_1_2_1_11_1","volume-title":"Elements Of Finite Model Theory","author":"Libkin Leonid","unstructured":"Leonid Libkin . 2004. Elements Of Finite Model Theory . Springer , Heidelberg . Leonid Libkin. 2004. Elements Of Finite Model Theory. Springer, Heidelberg."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"e_1_2_1_13_1","unstructured":"R. McNaughton and S. Papert. 1971. Counter-free Automata. MIT Press Cambridge MA.   R. McNaughton and S. Papert. 1971. Counter-free Automata. MIT Press Cambridge MA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"e_1_2_1_17_1","volume-title":"Formal Logic, and Circuit Complexity","author":"Straubing Howard","unstructured":"Howard Straubing . 1994. Finite Automata , Formal Logic, and Circuit Complexity . Birkh\u00e4user , Boston . Howard Straubing. 1994. Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston."},{"key":"e_1_2_1_18_1","first-page":"326","article-title":"Finite automata and logic of monadic predicates","volume":"140","author":"Trakhtenbrot Boris Avraamovich","year":"1961","unstructured":"Boris Avraamovich Trakhtenbrot . 1961 . Finite automata and logic of monadic predicates . Doklady Akademii Nauk SSSR 140 (1961), 326 -- 329 . In Russian. Boris Avraamovich Trakhtenbrot. 1961. Finite automata and logic of monadic predicates. Doklady Akademii Nauk SSSR 140 (1961), 326--329. In Russian.","journal-title":"Doklady Akademii Nauk SSSR"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2946799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2946799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:02Z","timestamp":1750223222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2946799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,15]]}},"alternative-id":["10.1145\/2946799"],"URL":"https:\/\/doi.org\/10.1145\/2946799","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,10]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}