  We study the universality and inclusion problems for register automata over
equality data. We show that the universality and the inclusion problems can be
solved with 2-EXPTIME complexity when the input automata are without guessing
and unambiguous, improving on the currently best-known 2-EXPSPACE upper bound
by Mottet and Quaas. When the number of registers of both automata is fixed, we
obtain a lower EXPTIME complexity, also improving the EXPSPACE upper bound from
Mottet and Quaas for fixed number of registers. We reduce inclusion to
universality, and then we reduce universality to the problem of counting the
number of orbits of runs of the automaton. We show that the orbit-counting
function satisfies a system of bidimensional linear recursive equations with
polynomial coefficients (linrec), which generalises analogous recurrences for
the Stirling numbers of the second kind, and then we show that universality
reduces to the zeroness problem for linrec sequences. While such a counting
approach is classical and has successfully been applied to unambiguous finite
automata and grammars over finite alphabets, its application to register
automata over infinite alphabets is novel. We provide two algorithms to decide
the zeroness problem for bidimensional linear recursive sequences arising from
orbit-counting functions. Both algorithms rely on techniques from linear
non-commutative algebra. The first algorithm performs variable elimination and
has elementary complexity. The second algorithm is a refined version of the
first one and it relies on the computation of the Hermite normal form of
matrices over a skew polynomial field. The second algorithm yields an EXPTIME
decision procedure for the zeroness problem of linrec sequences, which in turn
yields the claimed bounds for the universality and inclusion problems of
register automata.
