Low rank MSO

Prelegent(ci)

Giannos Stamoulis

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

22 stycznia 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Low rank MSO

Seminarium

Seminarium „Teoria automatów”

---

We introduce a new logic for describing properties of graphs, which is called low rank MSO. This is the fragment of monadic second-order logic (MSO), in which set quantification is restricted to sets of bounded rank. We prove that over any class of graphs that is weakly sparse, low rank logic has the same expressive power as separator logic, which is another extension of first-order order logic that can talk about non-local behavior such as connectivity. We also compare the expressive power of low rank MSO with variants of separator logic that involve flips. This is joint work with Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski, and Marek Sokołowski.

 

---