Résumé | In the literature we find many computation models whose expressiveness goes beyond finite automata, however without attaining the full power of Turing machines. The common practice is to enrich finite automata with some internal memory (e.g. counters, clocks, stacks, etc.) that can be used to store, manipulate, and compare data from a potentially infinite domain. An intriguing model that results from this practice is the model of register automaton, which is essentially a finite automaton equipped with a finite number of registers. Register automata are used to recognize languages over infinite alphabets. The deterministic, unambiguous, and non-deterministic variants of these automata form a hierarchy of strictly increasing expressive power, where the bottom and top levels have, respectively, decidable and undecidable equivalence problems. Accordingly, the intermediate class of unambiguous register automata is an interesting object of study, since it is believed to be robust and algorithmically well-behaved.
In this talk I will present some preliminary results obtained with Thomas Colcombet and Michal Skrzypczak towards proving the following conjecture: unambiguous register automata have a decidable equivalence problem and form the largest subclass of non-deterministic register automata that is closed under complement. |