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.

---