  Weighted automata (WA) are an extension of finite automata that defines
functions from words to values in a given semi-ring. An alternative model that
is deterministic, called Cost Register Automata (CRA), was introduced by Alur
et al. It enriches deterministic finite automata with a finite number of
registers, which store values, are updated at each transition using the
operations of the semi-ring, and are combined to produce the output. The
expressiveness of a CRA depends on the number of its registers and the type of
register updates allowed for each of its transitions. In particular, the class
of functions computable by a CRA with register updates defined by linear (or
affine) maps correspond exactly with rational functions (functions computable
by a WA). A natural problem for CRA is the register minimization problem: given
a function defined by a CRA, what is the minimal number of registers needed to
realize this function?
  In this paper, we solve the register minimization problem for CRA over a
field with linear (or affine) register updates, using an algebraic invariant of
a WA introduced recently by Bell and Smertnig, the so-called the linear hull of
the automaton. This invariant being computable, we are able to explicitly
compute a CRA with linear (or affine) updates, using the minimal number of
registers.
  Using these techniques, we are also able to solve the more general CRA
minimisation problem: given a CRA and integers $k,d$, is there an equivalent
linear (resp.~affine) CRA using at most $k$ states and $d$ registers?
