LIPIcs.MFCS.2017.82.pdf
- Filesize: 232 kB
- 2 pages
Document
On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk)
Author
-
Part of:
Volume:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-01
Cite As Get BibTex
Michal Pilipczuk. On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk). In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 82:1-82:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.82
Abstract
This is an overview of the invited talk delivered at the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).
Subject Classification
Keywords
- monadic second-order logic
- treewidth
- recognizability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Mikołaj Bojańczyk and Michał Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In LICS'16, pages 407-416. ACM, 2016. Full version available as arXiv preprint 1605.03045.
-
Bruno Courcelle. The Monadic Second-Order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990.
-
Valentine Kabanets. Recognizability equals definability for partial k-paths. In ICALP'97, volume 1256 of LNCS, pages 805-815. Springer, 1997.
-
Denis Lapoire. Recognizability equals Monadic Second-Order definability for sets of graphs of bounded tree-width. In STACS'98, volume 1373 of LNCS, pages 618-628. Springer, 1998.
-
Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72(1):65-94, 1990.