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

 

Model checking separator logic on graphs that exclude a fixed topological minor.


Prelegent: Szymon Toruńczyk

2021-10-06 14:15

We consider separator logic on graphs introduced recently by Bojańczyk, and independently by Siebertz, Shrader, and Vigny. This logic extends first-order logic by atomic predicates of arity k+2, for each k, expressing that every path from a vertex s to a vertex t must pass through one of the vertices v_1,...,v_k. We prove that the model checking problem for this logic is fixed parameter tractable on every class of graphs that excludes a fixed topological minor. To this end, we decompose each graph from such a class in a treelike fashion and run a variant of a tree automaton on the obtained tree decomposition. This is joint work with Siebertz, Shrader, Mi. Pilipczuk, and Vigny.