Low rank MSO

Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2

We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…