On separation and unambiguity for register automata

Nondeterministic register automata introduced by Kaminski form one of the most natural models of recognition for data-labelled structures,
in particular data words. Although the emptiness problem is decidable
for them, they lack some closure properties (e.g. complement). Because of that, they cannot be used to prove a theorem in the spirit of the Büchi-Elgot-Trakhtenbrot result on equivalence between NFA and MSO. In the search of more robust classes of automata over data words, Colcombet conjectured that unambiguous register automata are closed under complement. The technical core of the problem turns out to resemble questions of separation.

During the talk I will introduce the respective classes of automata as
well as formulate some conjectures relating them. I will also present
the line of approaching these problems we followed with Colcombet,
Manuel, and Puppis. Unfortunately, we have not proved any of the
conjectures. However, I believe that we gained a lot of understanding
of the technical difficulties that underline these problems.