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.