Uniformisation and Choice Questions for Regular Languages

A uniformisation of a binary relation R⊆X×Y assigns to each element x of the domain of R a particular y∈Y such that the pair〈x,y〉is in the relation. The regular-uniformisation problem asks if, in the context of words or trees, every regular relation admits a uniformisation that is also regular, idefinable in Monadic Second-Order Logic (MSO). It is already known that the answer to this question is positive in the context of finite and infinite words. In this thesis, we search for possible generalisations of these results. First, we study the possibility of uniformising relations of finite words in fragments of First-Order Logic (FO), the formalism where one can quantify over positions but not over sets of positions. We rely on algebraic characterisations of these fragments in order to emphasise their limitations in providing uniformisations. We also discuss the decidability of uniformising given regular relations in some of these fragments. Second, we highlight the strong connection between uniformisations and the expressive power of the considered formalisms. Namely, among varieties of regular languages, the assumption that the given formalism has uniformisation property, already guarantees the full power of all regular languages. The notion of a variety of languages is a standard concept which guarantees certain natural closure properties, such as closure under Boolean operations. Third, we study the possibility to uniformise regular relations of words defined over finitary domains: those are the domains that are infinite but admit a particular kind of finite representation. We show that, over these domains, the only obstacle to regular uniformisations is the existence of non-trivial automorphisms, meaning bijective functions that preserve the order and that are not the identity function. We also prove that, in this context of finitary domains, the regular-uniformisation problem is equivalent to being able to define in MSO natural objects over the domain, such as choice functions and well orders. All these results provide a broad perspective on the notion of uniformisation in the realm of subclasses and variants of regular languages.