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

Speaker(s)

Janusz Schmude

Affiliation

Uniwersytet Warszawski

Date

Nov. 27, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---