Uniformization of MSO-definable relation on integers

Speaker(s)

Grzegorz Fabiański

Affiliation

Uniwersytet Warszawski

Date

Nov. 13, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We consider the problem to decide, whether a given MSO-definable relation R of the bi-infinite words (words over integers), there exist a MSO-definable function F (a functional relation between bi-infinite words) which uniformize it (meaning that if x R y then also x R f(x)).  

We argue that this problem is decidable.

---