An algebraic approach to equivalence of MSO transductions of graphs of bounded treewidth

Prelegent(ci)

Janusz Schmude

Afiliacja

Uniwersytet Warszawski

Termin

27 listopada 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

We prove MSO-transductions of graphs of bounded treewidth have decidable 
equivalence modulo fractional isomorphism with real coefficients (not necessarily nonnegative).
The main goal of this talk is to present a new approach to equivalence problem of MSO-transductions of graphs of bounded treewidth.
This approach relies on associating to a graph a list of polynomials or generating functions
which can be updated by a polynomial function after join and forget operation of sourced graphs.

This is joint work with Mikołaj Bojańczyk.

---