LIPIcs.STACS.2017.4.pdf
- Filesize: 332 kB
- 4 pages
Document
Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)
Author
-
Part of:
Volume:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-06
Cite As Get BibTex
Till Tantau. Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 4:1-4:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.4
Abstract
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's Theorem all monadic second-order ("in a certain logic") properties of graphs of bounded tree width ("structured in a certain way") can be solved in linear time ("with a certain amount of resources"). Such theorems have become a valuable tool 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. The talk is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space classes and parallel computation, and tries to give a flavor of the range of
Subject Classification
Keywords
- Algorithmic metatheorems
- Courcelle’s Theorem
- tree width
- monadic second-order logic
- logarithmic space
- parallel computations
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
- Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. URL: http://dx.doi.org/10.1007/s002249910009.
- Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pages 143-152, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
- Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184-1206, November 2001. URL: http://dx.doi.org/10.1145/504794.504798.
- Martin Grohe. Logic, graphs, and algorithms. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata: History and Perspectives, volume 2 of Texts in Logic and Games, pages 357-422. Amsterdam University Press, 2007. URL: http://www2.informatik.hu-berlin.de/~grohe/pub/meta-survey.pdf.
- Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics, volume 558 of Contemporary Mathematics, pages 181-206. American Mathematical Society, 2011. URL: http://www2.informatik.hu-berlin.de/~grohe/pub/grokre11.pdf.
- Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 89-98, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591851.
- Stephan Kreutzer. Algorithmic meta-theorems. In Javier Esparza, Christian Michaux, and Charles Steinhorn, editors, Finite and Algorithmic Model Theory, volume 379 of London Mathematical Society Lecture Note Series. Cambridge University Press, 2011. URL: http://logic.las.tu-berlin.de/Kreutzer/Publications/amt-survey.pdf.
- Till Tantau. A gentle introduction to applications of algorithmic metatheorems for space and circuit classes. Algorithms, 9(3):44, 2016. URL: http://www.mdpi.com/1999-4893/9/3/44, URL: http://dx.doi.org/10.3390/a9030044.
- Carsten Thomassen. On the presence of disjoint subgraphs of a specified type. Journal of Graph Theory, 12(1):101-111, 1988. URL: http://dx.doi.org/10.1002/jgt.3190120111.