{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:42:33Z","timestamp":1760211753848,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2016,7,9]],"date-time":"2016-07-09T00:00:00Z","timestamp":1468022400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs are structured in a certain way, then the problem can be solved with a certain amount of resources. As an example, by Courcelle\u2019s Theorem, all monadic second-order (\u201cin a certain logic\u201d) properties of graphs of bounded tree width (\u201cstructured in a certain way\u201d) can be solved in linear time (\u201cwith a certain amount of resources\u201d). Such theorems have become valuable tools in algorithmics: if a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. This paper is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space and circuit classes, and tries to give a flavor of the range of their applications.<\/jats:p>","DOI":"10.3390\/a9030044","type":"journal-article","created":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T09:47:19Z","timestamp":1468230439000},"page":"44","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes"],"prefix":"10.3390","volume":"9","author":[{"given":"Till","family":"Tantau","sequence":"first","affiliation":[{"name":"Institute for Theoretical Computer Science, Universit\u00e4t zu L\u00fcbeck, L\u00fcbeck 23562, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2016,7,9]]},"reference":[{"key":"ref_1","unstructured":"van Leeuwen, J. (1990). Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, MIT Press."},{"key":"ref_2","unstructured":"Grohe, M., Kreutzer, S., and Siebertz, S. (July, January 29). Deciding First-order Properties of Nowhere Dense Graphs. Proceedings of the 46th Annual ACM Symposium on Theory of Computing; STOC \u201914, Copenhagen, Denmark."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1145\/504794.504798","article-title":"Deciding First-order Properties of Locally Tree-decomposable Structures","volume":"48","author":"Frick","year":"2001","journal-title":"J. ACM"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","article-title":"Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width","volume":"33","author":"Courcelle","year":"2000","journal-title":"Theory Comput. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., and Tantau, T. (2010, January 23\u201326). Logspace Versions of the Theorems of Bodlaender and Courcelle. Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.21"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1002\/jgt.3190120111","article-title":"On the presence of disjoint subgraphs of a specified type","volume":"12","author":"Thomassen","year":"1988","journal-title":"J. Graph Theory"},{"key":"ref_7","first-page":"357","article-title":"Logic, Graphs, and Algorithms","volume":"Volume 2","author":"Flum","year":"2007","journal-title":"Logic and Automata: History and Perspectives, Texts in Logic and Games"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Grohe, M., and Kreutzer, S. (2009, January 5\u20138). Methods for Algorithmic Meta Theorems. Proceedings of the Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics: AMS-ASL Joint Special Session, Washington, DC, USA. In Contemporary Mathemetics; American Mathematical Society: Providence, RI, USA, 2011; Volume 558, pp. 181\u2013206.","DOI":"10.1090\/conm\/558\/11051"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Esparza, J., Michaux, C., and Steinhorn, C. (2011). Finite and Algorithmic Model Theory, London Mathematical Society Lecture Note Series, Cambridge University Press.","DOI":"10.1017\/CBO9780511974960"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Immerman, N. (1999). Descriptive Complexity, Springer.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L. (1988, January 15\u201317). NC-algorithms for graphs with small treewidth. Proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 1988), Amsterdam, The Netherlands. In Lecture Notes in Computer Science; Springer: Heidelberg, Germany, 2010; Volume 344. pp. 1\u201310.","DOI":"10.1007\/3-540-50728-0_32"},{"key":"ref_12","first-page":"43","article-title":"Generalized First-Order Spectra and Polynomial-Time Recognizable Sets","volume":"7","author":"Fagin","year":"1974","journal-title":"Complex. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","article-title":"The Complexity of First-order and Monadic Second-order Logic Revisited","volume":"130","author":"Frick","year":"2004","journal-title":"Ann. Pure Appl. Logic"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Buss, S.R. (1987, January 25\u201327). The Boolean formula value problem is in ALOGTIME. Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987), New York, NY, USA.","DOI":"10.1145\/28395.28409"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1391289.1391291","article-title":"Undirected connectivity in log-space","volume":"55","author":"Reingold","year":"2008","journal-title":"J. ACM"},{"key":"ref_17","unstructured":"Elberfeld, M., and Schweitzer, P. (2016, January 17\u201320). Canonizing Graphs of Bounded Tree Width in Logspace. Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orleans, France. In Leibniz International Proceedings in Informatics; Volume 47, pp. 32:1\u201332:14."},{"key":"ref_18","unstructured":"Das, B., Datta, S., and Nimbhorkar, P. (2010, January 4\u20136). Log-space Algorithms for Paths and Matchings in k-trees. Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Nancy, France. In Leibniz International Proceedings in Informatics; Volume 5, pp. 215\u2013226."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1145\/972639.972646","article-title":"Existential second-order logic over graphs: Charting the tractability frontier","volume":"51","author":"Gottlob","year":"2004","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Tantau, T. (2015, January 4\u20137). Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification. Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Garching, Germany. In Leibniz International Proceedings in Informatics (LIPIcs); Volume 30, pp. 703\u2013715."},{"key":"ref_21","unstructured":"Elberfeld, M., Jakoby, A., and Tantau, T. (March, January 29). Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Paris, France. In Leibniz International Proceedings in Informatics (LIPIcs); Volume 14, pp. 66\u201377."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(88)90148-2","article-title":"Input-driven languages are in log n depth","volume":"26","author":"Dymond","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Krebs, A., Limaye, N., and Mahajan, M. (2010, January 19\u201321). Counting Paths in VPA Is Complete for #NC1. Proceedings of the 16th Annual International Conference on Computing and Combinatorics (COCOON 2010), Nha Trang, Vietnam. In Lecture Notes in Computer Science; Springer: Heidelberg, Germany, 2010; Volume 6196, pp. 44\u201353.","DOI":"10.1007\/978-3-642-14031-0_7"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","article-title":"A taxonomy of problems with fast parallel algorithms","volume":"64","author":"Cook","year":"1985","journal-title":"Inf. Control"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., and Nederlof, J. (2010, January 6\u20138). Saving space by algebraization. Proceedings of the 42nd ACM Symposium on Theory of computing (STOC 2010), Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806735"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/44\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:25:46Z","timestamp":1760210746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,9]]},"references-count":25,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["a9030044"],"URL":"https:\/\/doi.org\/10.3390\/a9030044","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,7,9]]}}}