Uniformization gives the full strength of regular languages

Speaker(s)

Vincent Michielini

Affiliation

Uniwersytet Warszawski

Date

June 12, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---