On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk)

Author Michal Pilipczuk



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.82.pdf
  • Filesize: 232 kB
  • 2 pages

Document Identifiers

Author Details

Michal Pilipczuk

Cite AsGet 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).
Keywords
  • monadic second-order logic
  • treewidth
  • recognizability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. Bruno Courcelle. The Monadic Second-Order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  3. Valentine Kabanets. Recognizability equals definability for partial k-paths. In ICALP'97, volume 1256 of LNCS, pages 805-815. Springer, 1997. Google Scholar
  4. 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. Google Scholar
  5. Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72(1):65-94, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail