{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:41Z","timestamp":1750306361761,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,17]],"date-time":"2016-02-17T00:00:00Z","timestamp":1455667200000},"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 SIGLOG News"],"published-print":{"date-parts":[[2016,2,17]]},"abstract":"<jats:p>It is well known that monadic-second order logic (MSO) expresses many natural NP-complete problems. However, a famous theorem of Courcelle states that every problem expressible in MSO can be solved in linear time for input graphs whose tree width is bounded by a fixed constant [Courcelle 1990]. Courcelle's Theorem is the prototypical example of an algorithmic \"meta theorem\", which states an algorithmic upper bound for a whole family of problems. This column reviews a series of meta theorems several of which refine Courcelle's Theorem by more precisely classifying the complexity of natural families of problems.<\/jats:p>","DOI":"10.1145\/2893582.2893588","type":"journal-article","created":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T14:26:47Z","timestamp":1585924007000},"page":"23-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Variants of Courcelle's Theorem for complexity classes inside P"],"prefix":"10.1145","volume":"3","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[{"name":"RWTH Aachen University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/647669.730998"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90057-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90018-6"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle Bruno","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","unstructured":"Michael Elberfeld. 2012. Space and Circuit Complexity of Monadic Second-Order Definable Problems on Tree-Decomposable Structures. Universitt zu L\u00fcbeck. Dissertation. Michael Elberfeld. 2012. Space and Circuit Complexity of Monadic Second-Order Definable Problems on Tree-Decomposable Structures. Universitt zu L\u00fcbeck. Dissertation."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.21"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) (Leibniz International Proceedings in Informatics)","volume":"14","author":"Elberfeld Michael","year":"2012"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591865"},{"key":"e_1_2_1_12_1","unstructured":"Michael Elberfeld and Pascal Schweitzer. 2015. Canonizing Graphs of Bounded Tree Width in Logspace. In Proceedings of the 33nd International Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Leibniz International Proceedings in Informatics). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. to appear. Michael Elberfeld and Pascal Schweitzer. 2015. Canonizing Graphs of Bounded Tree Width in Logspace. In Proceedings of the 33nd International Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Leibniz International Proceedings in Informatics). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. to appear."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer Berlin Heidelberg. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-29953-X J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer Berlin Heidelberg. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-29953-X","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_2_1_14_1","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059520"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11051"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"volume":"319","volume-title":"Proceedings of the Aegean Workshop on Computing: 3rd International Workshop on Parallel Computation and VLSI Theory. Lecture Notes in Computer Science","author":"Ibarra Oscar H.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00017-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647200.718725"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645714.664805"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120111"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer Berlin Heidelberg. Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1022"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2893582.2893588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2893582.2893588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:14Z","timestamp":1750222574000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2893582.2893588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,17]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,17]]}},"alternative-id":["10.1145\/2893582.2893588"],"URL":"https:\/\/doi.org\/10.1145\/2893582.2893588","relation":{},"ISSN":["2372-3491"],"issn-type":[{"type":"electronic","value":"2372-3491"}],"subject":[],"published":{"date-parts":[[2016,2,17]]},"assertion":[{"value":"2016-02-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}