{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T23:06:53Z","timestamp":1663110413689},"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":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2016,11,15]]},"abstract":"\n We study on which classes of graphs first-order logic (\n fo<\/jats:sc>\n ) and monadic second-order logic (\n 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 fo<\/jats:sc>\n and\n 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 induced<\/jats:italic>\n subgraphs, we show an analogous result for guarded second-order logic (\n gso<\/jats:sc>\n ), the variant of\n 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","source":"Crossref","is-referenced-by-count":3,"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"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[{"name":"Universit\u00e4t zu L\u00fcbeck, L\u00fcbeck, Germany"}]}],"member":"320","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"},{"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"},{"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"},{"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","doi-asserted-by":"crossref","volume-title":"Elements Of Finite Model Theory","author":"Libkin Leonid","DOI":"10.1007\/978-3-662-07003-1"},{"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"},{"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","journal-title":"Doklady Akademii Nauk SSSR"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2946799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T22:05:14Z","timestamp":1614636314000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2946799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,15]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,15]]}},"alternative-id":["10.1145\/2946799"],"URL":"http:\/\/dx.doi.org\/10.1145\/2946799","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":["Computational Mathematics","Logic","General Computer Science","Theoretical Computer Science"],"published":{"date-parts":[[2016,11,15]]}}}