Nie jesteś zalogowany | Zaloguj się

Uniformization and selection for FO and MSO

Prelegent(ci)
Michał Skrzypczak
Afiliacja
Uniwersytet Warszawski
Termin
19 grudnia 2012 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

Uniformization problem asks whether for a given formula phi(X,Y) there exists a formula psi(X,Y) that for every X selects exactly one Y satisfying phi(X,Y). Quite natural arguments show that MSO logic has uniformization property in finite and infinite words. During this talk I will survey classical results in the area. Additionally, I plan to present some new (and simple) observations; one of them states that FO does not have uniformization property even in finite words.