The Containment Problem for Unambiguous Register Automata

We investigate the complexity of the containment problem:
given a register automaton A and an unambiguous register automaton B,

is the language accepted by A contained in the language accepted by B?
We prove that the problem is decidable and give upper bounds on the computational complexity.
We also study the case where the register automata are defined over ordered domains,
and where the registers can take values that did not occur in the input word (so called register automata with guessing). 

 

This is joint work with Antoine Mottet (Charles University, Prague).