Weitere Informationen zum ausgewählten Vortrag

Graphs of bounded shrub-depth and first-order logic

Jörg Flum

Mittwoch, 11. Dezember 2019 16:30Uhr

We show that the expressive power of monadic second-order logic (MSO) and of first-order logic (FO) coincide on classes of graphs of bounded shrub-depth. Moreover we explain in what sense these classes are maximal classes with MSO = FO.