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.

---