Nie jesteś zalogowany | Zaloguj się

Monadic MSO logic

Prelegent(ci)
Bartek Klin
Afiliacja
Uniwersytet Warszawski
Termin
15 kwietnia 2020 14:15
Informacje na temat wydarzenia
Online seminar
Seminarium
Seminarium „Teoria automatów”

The correspondence of regular languages and monadic second-order logic relies on the fact that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for finite words, but also for infinite words, finite or infinite trees, and more generally for a wide range of monads. However, it does not hold always, and a structural characterization of those monads for which it does hold seems elusive. I will focus on a few examples to illustrate how subtle the condition can be.