Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Some results and directions in finite model theory

Prelegent: Szymon Toruńczyk

2021-11-10 14:15

I will discuss the FO-transduction order on classes of graphs (or other structures), defined by the relation: a class C can be obtained by an FO-transduction from a class D. I will focus on the interplay of this order with notions such as treewidth, clique-width, twin-width, bounded expansion, nowhere denseness, monadic stability, monadic NIP. I will state some known results and pose several conjectures. For example, one of the conjectures is a strengthening of a conjecture of Seese regarding MSO transductions.