You are not logged in | Log in

Uniformization and selection for FO and MSO

Speaker(s)
Michał Skrzypczak
Affiliation
Uniwersytet Warszawski
Date
Dec. 19, 2012, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

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.