joint work with Achim Blumensath and Thomas Colcombet

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