joint work with Achim Blumensath and Thomas Colcombet

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Nov. 6, 2013, 2:15 p.m.

Room

room 5870

Title in Polish

Asymptotic MSO and lossy tiling problems

Seminar

Seminar Automata Theory

---

I will talk about a new extension of the MSO logic in the style of MSO+U, which is called Asymptotic MSO. This logic refers to structures (in particular omega-words) whose elements are weighted with natural numbers; the logic can express constraints on these values. I will first list some results concerning the expressive power of this logic. Then, I will show that we can decide the satisfiability problem for a fragment of this logic. The proof goes via a reduction to a "lossy tiling problem".

---