You are not logged in | Log in

Considering the following question: given (in a sense which will be

clarified in the talk) a countable totally ordered set D, on which

condition(s) does there exist a choice function over D (i.e. a

function f: P(D) -> D such that for all nonempty X subset of D, f(X)

is in X) definable by an MSO-formula phi(X,x) (where X is a nonempty

subset of X and x is the element f(X))?

This question is closely related to another question which asks on

which condition(s) all regular word-relations R ⊆ A^D x B^D

(identified with regular languages ⊆ (AxB)^D) admit a regular

uniformisation (or selection), meaning another regular relation F ⊆ R

which selects for each word w in the projection of R a particular word

sigma in B^D satisfying (w,sigma) ∈ R.

It is already known that this regular-uniformisation property is true

for finite words and for omega-words. In the talk, we generalize this

result by answering these two questions, and we provide a way to

construct uniformisations and choice functions when it is possible.

joint work with Michał Skrzypczak