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.