Model checking separator logic on graphs that exclude a fixed topological minor.
- Speaker(s)
- Szymon Toruńczyk
- Affiliation
- MIM UW
- Date
- Oct. 6, 2021, 2:15 p.m.
- Room
- room 5050
- Seminar
- Seminar Automata Theory
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.