Uniformization gives the full strength of regular languages

Prelegent(ci)

Vincent Michielini

Afiliacja

Uniwersytet Warszawski

Termin

12 czerwca 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

Given R a binary relation between words (which we treat as a language over a product alphabet A × B),
 a uniformisation of it is a language L ⊆ R that  chooses a single word over B, for each word over A.
It is known that MSO, the full class of regular languages,
is strong enough to define a uniformization for each of its relations. 
The question of uniformisation is a quest of other formalisms, weaker 
than MSO, which also have this property. We solve this problem for 
pseudo-varieties of semigroups (pvs): we show that no nonempty pvs 
weaker than MSO can provide uniformizations for its relations.
We also extend the uniformization problem to words of nonfinite domain:
given an enumerable set, in which condition can we define a single element 
of it with an MSO-sentence?

 

This is joint work with Nathan Lhote and Michał Skrzypczak.

---