Asymptotic MSO and lossy tiling problems

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

6 listopada 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Achim Blumensath and Thomas Colcombet

Seminarium

Seminarium „Teoria automatów”

---

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".

---