Aix Marseille Univ, CNRS, LIS, Marseille, Franceyahia-idriss.benalioua@lis-
lab.frAix Marseille Univ, CNRS, LIS, Marseille<EMAIL_ADDRESS>Aix Marseille Univ, CNRS, LIS, Marseille, Francepierre-alain.reynier@lis-
lab.fr Yahia Idriss Benalioua, Nathan Lhote and Pierre-Alain Reynier Theory of
computation Formal languages and automata theory Automata extensions
Quantitative automata This is the full version of a paper accepted at MFCS
2024 This work has been partly funded by the QuaSy project (ANR-23-CE48-0008).
Rastislav Královič and Antonín Kučera 2 49th International Symposium on
Mathematical Foundations of Computer Science (MFCS 2024) MFCS 2024 MFCS 2024
August 26–30, 2024 Bratislava, Slovakia 306 16

# Minimizing Cost Register Automata over a Field

Yahia Idriss Benalioua  Nathan Lhote  Pierre-Alain Reynier

###### Abstract

Weighted automata ($\mathrm{WA}$) are an extension of finite automata that
define functions from words to values in a given semiring. An alternative
deterministic model, called Cost Register Automata ($\mathrm{CRA}$), was
introduced by Alur et al. It enriches deterministic finite automata with a
finite number of registers, which store values, updated at each transition
using the operations of the semiring. It is known that $\mathrm{CRA}$ with
register updates defined by linear maps have the same expressiveness as
$\mathrm{WA}$. Previous works have studied the register minimization problem:
given a function computable by a $\mathrm{WA}$ and an integer $k$, is it
possible to realize it using a $\mathrm{CRA}$ with at most $k$ registers?

In this paper, we solve this problem for $\mathrm{CRA}$ over a field with
linear register updates, using the notion of linear hull, an algebraic
invariant of $\mathrm{WA}$ introduced recently by Bell and Smertnig. We then
generalise the approach to solve a more challenging problem, that consists in
minimizing simultaneously the number of states and that of registers. In
addition, we also lift our results to the setting of $\mathrm{CRA}$ with
affine updates. Last, while the linear hull was recently shown to be
computable by Bell and Smertnig, no complexity bounds were given. To fill this
gap, we provide two new algorithms to compute invariants of $\mathrm{WA}$.
This allows us to show that the register (resp. state-register) minimization
problem can be solved in 2-ExpTime (resp. in NExpTime).

###### keywords:

Weighted automata, Cost Register automata, Zariski topology

###### category:

##  1 Introduction

Weighted automata ($\mathrm{WA}$) are a quantitative extension of finite state
automata and have been studied since the sixties [16]. These automata define
functions from words to a given semiring: each transition has a weight in the
semiring and the weight of an execution is the product of the weights of the
transitions therein; the non-determinism of the model is handled using the sum
of the semiring: the weight associated with a word is the sum of the weights
of the different executions over this word. Functions realized by weighted
automata are called rational series. This fundamental model has been widely
studied during the last decades [13]. While some expressiveness results can be
obtained in a general framework (such as the equivalence with rational
expressions), the decidability status of important problems heavily depends on
the considered semiring. Amongst the classical problems of interest, one can
mention _equivalence_ , _sequentiality_ (resp. _unambiguity_), which aims at
determining whether there exists an equivalent deterministic (resp.
unambiguous) $\mathrm{WA}$, and _minimization_ , which aims at minimizing the
number of states.

Weighted automata over a field (e.g. the field of rationals $\mathbb{Q}$)
enjoy many nice properties: the equivalence of weighted automata is decidable
and they can be minimized, and both can be done efficiently (see e.g. [15,
Theorem 4.10 and Corollary 4.17 (Chapter III)]). The sequentiality and
unambiguity are also decidable, as shown recently in [3, 4], with no
complexity bounds however. The most studied semirings which are not fields are
the tropical semirings and the semiring of languages, and in both cases
equivalence is undecidable (see [8, Section 3] and [5, Theorem 8.4]) and no
minimization algorithm is known. Regarding sequentiality, partial decidability
results have been obtained for these semirings using the notion of twinning
property [6, 14].

Cost register automata ($\mathrm{CRA}$) have been introduced more recently by
Alur et al. [1]. A cost register automaton is a deterministic finite state
automaton endowed with a finite number of registers storing values from the
semiring. The registers are initialized by some values, then at each
transition the values are updated using the operations and constants of the
semiring. Several fragments of $\mathrm{CRA}$ can be considered by restricting
the operations allowed. For instance, an easy observation is that
$\mathrm{WA}$ are exactly $\mathrm{CRA}$ with one state (however, one can
observe that adding states does not extend expressiveness) and linear updates,
_i.e._ updates of the form $X\coloneqq\sum_{i=1}^{k}X_{i}*c_{i}$ (intuitively,
the new values of the registers only depend linearly on the previous ones).
Thus, the model of linear $\mathrm{CRA}$ is an alternative to $\mathrm{WA}$
which allows to trade non-determinism for registers.

The register minimization problem. As $\mathrm{CRA}$ are finite state automata
extended with registers storing elements from the semiring, it is natural to
aim at minimizing the number of registers used. For a given class
$\mathcal{C}$ of $\mathrm{CRA}$, this problem asks, given a $\mathrm{WA}$ and
a number $k$, whether there exists an equivalent $\mathrm{CRA}$ in
$\mathcal{C}$ with at most $k$ registers. From a practical point of view,
reducing the number of registers allows to reduce the memory usage, since a
register can require unbounded memory. From a theoretical point of view, this
problem can be understood as a refinement of the classical problem of
minimization of WA. Indeed, a $\mathrm{WA}$ can be translated into a linear
CRA with a single state, and as many registers as the number of states of the
$\mathrm{WA}$. This problem has been studied in [2, 10, 9] for three different
models of $\mathrm{CRA}$ but in all these works, the additive law of the
semiring is not allowed (_i.e._ updates of the form $X\coloneqq Y+Z$ are
forbidden). It is worth noticing that [10] encompasses the case of
$\mathrm{CRA}$ over a field, with only updates of the form $X\coloneqq Y*c$,
with $c$ an element of the field.

While the minimal number of registers needed to realise a $\mathrm{WA}$ (also
known as the _register complexity_) is upper bounded by the number of states
of a minimal $\mathrm{WA}$, it may be possible to build an equivalent
$\mathrm{CRA}$ with fewer registers, but more states. Hence there is a
_tradeoff_ between the number of states and the number of registers. This
leads to the following _state-register minimization problem for
$\mathrm{CRA}$_ which asks, for a class $\mathcal{C}$ of $\mathrm{CRA}$, given
a $\mathrm{WA}$ and integers $n,k$ whether an equivalent $\mathrm{CRA}$ in
$\mathcal{C}$ with $n$ states and $k$ registers can be constructed. In this
framework, the classical minimization of $\mathrm{WA}$ corresponds to
minimizing the number of registers while using only one state, for the class
of linear $\mathrm{CRA}$.

The linear hull. As mentioned before, the case of fields is well-behaved to
obtain decidability results. In their recent work [3], Bell and Smertnig
introduced the notion of _linear hull_ of a $\mathrm{WA}$. This notion is
inspired by the algebraic theory needed to study polynomial automata but cast
into a linear setting. A linear algebraic set (aka linear Zariski closed set)
is a finite union of vector subspaces: we later call them _Z-linear sets_.
Given a Z-linear set $S=\bigcup_{i=1}^{p}V_{i}$, the dimension of $S$ is the
maximum of the dimensions of the $V_{i}$’s. In this work, the size of the
union, $p$, is called the length of $S$. Observe that such Z-linear sets were
also used in [7] for a category-theoretic approach to minimization of weighted
automata over a field. We say such a set is an invariant if it contains the
initial vector and is stable under the updates of the automaton. Then the
linear hull of a weighted automaton is the strongest Z-linear invariant. In
[3], Bell & Smertnig show that computing the linear hull of a minimal
automaton allows to decide sequentiality and unambiguity. In addition, in [4],
they show that the linear hull can effectively be computed, without providing
complexity bounds however.

Contributions. In this work, we deepen the analysis of the linear hull of a
$\mathrm{WA}$ in order to solve the register and state-register minimization
problems for linear $\mathrm{CRA}$. In addition, we also provide new
algorithms to compute the linear hull which come with complexity upper bounds,
which can be used to derive complexity results for minimization problems as
well as for sequentiality and unambiguity of $\mathrm{WA}$. More precisely,
our contributions are as follows:

  * •

Firstly, we show that _the register minimization problem_ for the class of
linear $\mathrm{CRA}$ over a field can be solved in 2-ExpTime. To this end,
given a rational series $f$, we show that the minimal number of registers
needed to realize $f$ using a linear $\mathrm{CRA}$ is exactly the dimension
of the linear hull of a minimal $\mathrm{WA}$ of $f$. We then show that the
linear hull of a $\mathrm{WA}$ can be computed in 2-ExpTime. We show that this
complexity drops down to ExpTime for the particular case of commuting
transition matrices (which includes the case of a single letter alphabet),
with a matching lower bound.

  * •

As a consequence of the computation of the linear hull of a $\mathrm{WA}$ and
of results proved in [3], we obtain a 2-ExpTime upper bound for the problems
of _sequentiality and unambiguity of weighted automata_ over a field, closing
a question raised in [4].

  * •

Secondly, we prove that the _state-register minimization problem_ for linear
$\mathrm{CRA}$ can be solved in NExpTime. More precisely, given a minimal
$\mathrm{WA}$ $A$, we show a correspondence between Z-linear invariants of $A$
and linear $\mathrm{CRA}$ equivalent to $A$. This correspondence maps the
length (resp. dimension) of the invariant to the number of states (resp.
registers) of the equivalent linear $\mathrm{CRA}$. We then provide a
(constructive) NExpTime algorithm that, given a minimal $\mathrm{WA}$ and two
integers $n,k$, guesses a well-behaved invariant allowing to exhibit a
satisfying equivalent $\mathrm{CRA}$.

  * •

Last, we actually present these results in a more general setting, by
considering _affine_ $\mathrm{CRA}$, which are a slight extension of linear
$\mathrm{CRA}$ allowing to use affine maps in the updates of the registers.

Outline of the paper. We present the models of weighted automata and cost
register automata in Section 2. We then formally define the two problems we
consider, _i.e._ register and state-register minimization problems, and state
our main results in Section 3. In Section 4, we introduce the necessary
topological notions to define Z-linear/Z-affine set and invariants of weighted
automata, and detail our characterizations of the register and state-register
complexities of a rational series. Finally in Section 5, we present our
algorithms, as well as their consequences in terms of decidability and
complexity for the two problems we consider. Omitted proofs and more details
for Sections 4 and 5 can be found in the appendix.

##  2 Weighted Automata and Cost Register Automata

Basic concepts and notations. An alphabet $\Sigma$ is a finite set of letters.
The set of finite words over $\Sigma$ will be denoted by $\Sigma^{*}$, the
empty word by $\epsilon$ and, for two words $u$ and $v$, $uv$ will denote
their concatenation. For two sets $X$ and $Y$, we denote by $X\times Y$ their
cartesian product and by $\pi_{X}\colon X\times Y\to X$ and $\pi_{Y}\colon
X\times Y\to Y$ we denote the canonical projection on $X$ and $Y$
respectively. The set nonnegative integers will be denoted by $\mathbb{N}$.
For two integers $i,j$, we will denote by $\llbracket i,j\rrbracket$ the
interval of integers between $i$ and $j$ (both included).

A _semigroup_ $(S,*)$ is a set $S$ together with an associative binary
operation $*$. If $(S,*)$ has an identity element $e$, $(S,*,e)$ is called a
_monoid_ and if, moreover, every element has an inverse, $(S,*,e)$ is called a
_group_. If there is no ambiguity, we will identify algebraic structures with
the set that they are defined on. A semigroup (or a monoid/group) is said to
be _commutative_ if its law is. A sub-semigroup (or submonoid/subgroup) of $S$
is a subset of $S$ that is a semigroup (or a monoid/group). Given $E\subseteq
S$, the monoid _generated_ by $E$, denoted $\left<E\right>$, is the smallest
sub-monoid of $S$ containing $E$.

A _field_ $(\mathbb{K},+,\cdot)$ is a structure where $(\mathbb{K},+,0)$ and
$(\mathbb{K}\setminus\left\\{0\right\\},\cdot,1)$ are commutative groups and
multiplication distributes over addition. In this work, we will consider
$\mathbb{K}$ as the field of rational numbers $\mathbb{Q}$, or any finite
field extension of $\mathbb{Q}$, to perform basic operations in polynomial
time. For all $n\in\mathbb{N}$, $\mathbb{K}^{n}$ is an $n$-dimensional _vector
space_ over the field $\mathbb{K}$. We will work with row vectors and apply
matrices on the right, and we will identify linear maps (resp. linear forms)
with their corresponding matrices (resp. column vectors). The set of $n$ by
$m$ matrices over $\mathbb{K}$ will be denoted by $\mathbb{K}^{n\times m}$,
and $\mathbb{K}^{1\times n}$ (or simply $\mathbb{K}^{n}$ when there is no
ambiguity) will denote the set of $n$-dimensional vectors. For any matrix $M$
(resp. vector $v$), and indices $i$ and $j$, $M_{i,j}$ (resp. $v_{i}$) will
denote the value of the entry in the $i$-th row and the $j$-th column of $M$
(resp. the $i$-th entry of $v$). Matrix transposition will be denoted by
$M^{t}$. A _vector subspace_ of $\mathbb{K}^{n}$ is a subset of
$\mathbb{K}^{n}$ stable by linear combinations and for all subsets $E$ of
$\mathbb{K}^{n}$, $\textup{{span}}\left(E\right)$ will denote the smallest
vector subspace of $\mathbb{K}^{n}$ containing $E$ (if $E$ contains a single
vector $(x_{1},\dots,x_{n})$, $\textup{{span}}\left(E\right)$ will be denoted
by $\textup{{span}}\left(x_{1},\dots,x_{n}\right)$).

$\mathbb{K}^{n}$ can also be seen as an $n$-dimensional _affine space_. Affine
maps $f\colon\mathbb{K}^{n}\to\mathbb{K}^{m}$ are maps of the form
$f(u)=uf^{(l)}+f^{(a)}$ where $f^{(l)}\in\mathbb{K}^{n\times m}$ and
$f^{(a)}\in\mathbb{K}^{1\times m}$. An _affine subspace_ $A$ of
$\mathbb{K}^{n}$ is a subset of $\mathbb{K}^{n}$ of the form $A=p+V$ with
$p\in A$ and $V$ a vector subspace of $\mathbb{K}^{n}$. They are stable by
affine combinations (linear combinations with coefficients adding up to 1).
For all $E\subseteq\mathbb{K}^{n}$, $\textup{{aff}}\left(E\right)$ will denote
the smallest affine subspace of $\mathbb{K}^{n}$ containing $E$.

Weighted Automata. Let $\Sigma$ be a finite alphabet and
$(\mathbb{K},+,\cdot)$ be a field.

######  Definition 2.1 (Weighted Automaton).

A _Weighted Automaton_ ($\mathrm{WA}$ for short) of dimension $d$, on $\Sigma$
over $\mathbb{K}$, is a triple $\mathcal{R}=(u,\mu,v)$, where
$u\in\mathbb{K}^{1\times d}$, $v\in\mathbb{K}^{d\times 1}$ and
$\mu\colon\Sigma^{*}\to\mathbb{K}^{d\times d}$ is a monoid morphism. We will
call $u$ and $v$ the _initial_ and _terminal_ vectors respectively and
$\mu(a)$, for $a\in\Sigma$, will be called a _transition matrix_. A
$\mathrm{WA}$ realizes a _formal power series_ over $\Sigma^{*}$ with
coefficients in $\mathbb{K}$ (a function from $\Sigma^{*}$ to $\mathbb{K}$)
defined, for all $w\in\Sigma^{*}$, by
$\left\llbracket\mathcal{R}\right\rrbracket(w)=u\mu(w)v$. Any series that can
be realized by a $\mathrm{WA}$ will be called _rational_.

$q_{1}$$q_{2}$$a:2$$a:2$$1$$1$

Figure 1: The WA of Example 2.2.

$\mathrm{WA}$ also have a representation in terms of finite-state automata, in
which transitions are equipped with weights. We then say that a $\mathrm{WA}$
is sequential (resp. unambiguous) when its underlying automaton is. Formally,
we say that a $\mathrm{WA}$ $\mathcal{R}=(u,\mu,v)$ is _sequential_ when $u$
has a single non-zero entry and, for each letter $a$, and each index $i$,
there is at most one index $j$ such that $\mu(a)_{i,j}\neq 0$.

######  Example 2.2.

We consider the $\mathrm{WA}$, on the alphabet $\\{a\\}$ and over the field of
real numbers, $\mathcal{R}=(u,\mu,v)$ with $u=(1,0)$, $v=(1,0)^{t}$, and
$\mu(a)=\begin{pmatrix}0&2\\\ 2&0\end{pmatrix}$. One can verify that the
function realized by this $\mathrm{WA}$ maps the word $a^{n}$ to $2^{n}$ if
$n$ is even, and to $0$ otherwise. It can be represented graphically by the
automaton depicted on Figure 1.

A $\mathrm{WA}$ realizing a rational series $f$ is said to be _minimal_ if its
dimension is minimal among all the $\mathrm{WA}$ realizing $f$. We also have
the following characterization of minimal $\mathrm{WA}$ (see [15, Proposition
4.8 (Chapter III)]):

######  Proposition 2.3.

Let $\mathcal{R}=(u,\mu,v)$ be a $d$-dimensional $\mathrm{WA}$ and let
$\textup{{LR}}\left(\mathcal{R}\right)=u\mu(\Sigma^{*})=\left\\{u\mu(w)\,\middle|\,w\in\Sigma^{*}\right\\}$
be its (left) _reachability set_ and
$\textup{{RR}}\left(\mathcal{R}\right)=\mu(\Sigma^{*})v$ be its right
reachability set.

$\mathcal{R}$ is a minimal $\mathrm{WA}$ if and only if
$\textup{{span}}\left(\textup{{LR}}\left(\mathcal{R}\right)\right)=\mathbb{K}^{1\times
d}$ and
$\textup{{span}}\left(\textup{{RR}}\left(\mathcal{R}\right)\right)=\mathbb{K}^{d\times
1}$.

Expressions, substitutions and Cost Register Automata. For a field
$(\mathbb{K},+,\cdot)$ and a finite set of variables $\mathcal{X}$ disjoint
from $\mathbb{K}$, let $\textup{{Exp}}(\mathcal{X})$ denote the set of
expressions generated by the grammar $e\Coloneqq k\,|\,X\,|\,e+e\,|\,e\cdot
e$, where $k\in\mathbb{K}$ and $X\in\mathcal{X}$. A _substitution_ over
$\mathcal{X}$ is a map $s\colon\mathcal{X}\to\textup{{Exp}}(\mathcal{X})$. It
can be extended to a map
$\textup{{Exp}}(\mathcal{X})\to\textup{{Exp}}(\mathcal{X})$ by substituting
each variable $X$ in the expression given as an input by $s(X)$. By
identifying $s$ with its extension, we can compose substitutions. We call
_valuations_ the substitutions of the form $v\colon\mathcal{X}\to\mathbb{K}$.
The set of substitutions over $\mathcal{X}$ will be denoted by
$\textup{{Sub}}(\mathcal{X})$ and the set of valuations
$\textup{{Val}}(\mathcal{X})$.

######  Definition 2.4 (Cost Register Automaton).

A _cost register automaton_ ($\mathrm{CRA}$ for short), on the alphabet
$\Sigma$ over the field $\mathbb{K}$, is a tuple
$\mathcal{A}=(Q,q_{0},\mathcal{X},v_{0},o,\delta)$ where $Q$ is a finite set
of _states_ , $q_{0}\in Q$ is the initial state, $\mathcal{X}$ is a finite set
of registers (variables), $v_{0}\in\textup{{Val}}(\mathcal{X})$ is the
registers’ initial valuation, $o\colon Q\to\textup{{Exp}}(\mathcal{X})$ is the
output function, and $\delta\colon Q\times\Sigma\to
Q\times\textup{{Sub}}(\mathcal{X})$ is the transition function. We will denote
by $\delta_{Q}\coloneqq\pi_{Q}\circ\delta$ the transition function of the
underlying automaton of the $\mathrm{CRA}$ and
$\delta_{\mathcal{X}}\coloneqq\pi_{\textup{{Sub}}(\mathcal{X})}\circ\delta$
its register update function.

$\mathcal{A}$ computes a function
$\llbracket\mathcal{A}\rrbracket\colon\Sigma^{*}\to\mathbb{K}$ defined as
follows: the configurations of $\mathcal{A}$ are pairs $(q,v)\in
Q\times\textup{{Val}}(\mathcal{X})$. The run of $\mathcal{A}$ on a word
$w=a_{1}\dots a_{n}\in\Sigma^{*}$ is the sequence of configurations
$(q_{i},v_{i})_{i\in\llbracket 0,n\rrbracket}$ where, $q_{0}$ is the initial
state, $v_{0}$ is the initial valuation and, for all $i\in\llbracket
1,n\rrbracket$, $q_{i}=\delta_{Q}(q_{i-1},a_{i})$ and
$v_{i}=v_{i-1}\circ\delta_{\mathcal{X}}(q_{i-1},a_{i})$. We then define
$\llbracket\mathcal{A}\rrbracket(w)=v_{n}(o(q_{n}))$.

$\delta$ can be extended to words by setting, for all $q\in Q$,
$\delta(q,\epsilon)=(q,id_{\mathcal{X}})$, where $id_{\mathcal{X}}$ is the
substitution such that $id_{\mathcal{X}}(X)=X$ for all $X\in\mathcal{X}$, and,
for all $a\in\Sigma$ and $w\in\Sigma^{*}$,
$\delta_{Q}(q,aw)=\delta_{Q}(\delta_{Q}(q,a),w)$ and
$\delta_{\mathcal{X}}(q,aw)=\delta_{\mathcal{X}}(q,a)\circ\delta_{\mathcal{X}}(\delta_{Q}(q,a),w)$.
We then have

$\llbracket\mathcal{A}\rrbracket(w)=v_{0}\circ\delta_{\mathcal{X}}(q_{0},w)(o(\delta_{Q}(q_{0},w)))$

######  Example 2.5 (Example 2.2 continued).

Two $\mathrm{CRA}$ are depicted on Figure 2. They are both on the alphabet
$\\{a\\}$ and over the field of real numbers, and both realize the same
function as the $\mathrm{WA}$ considered in Example 2.2.

$\left\\{\begin{aligned} X\coloneqq 1\\\ Y\coloneqq
0\end{aligned}\right.$$X$$a:\left\\{\begin{aligned} X\coloneqq Y\cdot 2\\\
Y\coloneqq X\cdot 2\end{aligned}\right.$

$0$$a:X\coloneqq X\cdot 2$$a:X\coloneqq X\cdot 2$$X\coloneqq 1$$X$

Figure 2: Two CRA detailed in Example 2.5. Registers are denoted by letters
$X,Y$.

An expression is called _linear_ if it has the form
$\sum_{i=1}^{k}\alpha_{i}X_{i}$, for some family of $\alpha_{i}\in\mathbb{K}$
and $X_{i}\in\mathcal{X}$, and if it has the form
$\sum_{i=1}^{k}\alpha_{i}X_{i}+\beta$, for some $\beta\in\mathbb{K}$, it is
called _affine_. We will denote by $\textup{{Exp}}_{\ell}(\mathcal{X})$ (resp.
$\textup{{Exp}}_{a}(\mathcal{X})$) the set of linear (resp. affine)
expressions.

######  Definition 2.6 (Linear/Affine $\mathrm{CRA}$).

A $\mathrm{CRA}$ $\mathcal{A}=(Q,q_{0},\mathcal{X},\allowbreak
v_{0},o,\delta)$ is called _linear_ if,
$\delta_{\mathcal{X}}(q,a)(X)\in\textup{{Exp}}_{\ell}(\mathcal{X})$ and
$o(q)\in\textup{{Exp}}_{\ell}(\mathcal{X})$, for all $q\in Q,a\in\Sigma$ and
$X\in\mathcal{X}$, and if
$\delta_{\mathcal{X}}(q,a)(X)\in\textup{{Exp}}_{a}(\mathcal{X})$ and
$o(q)\in\textup{{Exp}}_{a}(\mathcal{X})$, the $\mathrm{CRA}$ is called
_affine_.

Linear $\mathrm{CRA}$ are a particular case of affine $\mathrm{CRA}$ and,
given an affine $\mathrm{CRA}$ it is always possible to define an equivalent
linear $\mathrm{CRA}$ using one more register with a constant value of $1$ to
realize affine register updates in a linear way, thus :

######  Remark 2.7.

Linear and affine $\mathrm{CRA}$ have the same expressiveness.

The added cost of a register will however become relevant when we will
consider minimization problems in the next sections.

Observe that we can assume that
$\mathcal{X}=\left\\{X_{1},\dots,X_{k}\right\\}$ is ordered, and identify any
linear expression $e=\sum_{i=1}^{k}\alpha_{i}X_{i}$ (with the $\alpha_{i}$ not
present in the expression assumed to be 0) with the linear form
$\underline{e}\colon\mathbb{K}^{k}\to\mathbb{K}$ defined by the column vector
$(\alpha_{1},\dots,\alpha_{k})^{t}$. We can then identify any linear
substitution $s\colon\mathcal{X}\to\textup{{Exp}}_{\ell}(\mathcal{X})$ with
the linear map $\underline{s}\colon\mathbb{K}^{k}\to\mathbb{K}^{k}$ defined by
the block matrix $(\underline{s(X_{1})}|\cdots|\underline{s(X_{k})})$, and we
can identify any valuation $v\colon\mathcal{X}\to\mathbb{K}$ with the vector
$\underline{v}=(v(X_{1}),\cdots,v(X_{k}))$ of the vector space
$\mathbb{K}^{k}$.

In the following, we will drop the underline notation and make the
identifications implicitly.

Thanks to these observations, the registers of a linear $\mathrm{CRA}$ and
their updates can be characterized by the values of the vector associated with
$v_{0}$, and the linear maps associated with the $\delta_{\mathcal{X}}(q,a)$
and $o(q)$, for all $q\in Q$ and $a\in\Sigma$, and we can check that

$\llbracket\mathcal{A}\rrbracket(w)=v_{0}\ \delta_{\mathcal{X}}(q_{0},w)\
o(\delta_{Q}(q_{0},w))$

We can also identify affine expressions with affine forms and affine
substitutions with affine maps to simplify dealing with affine $\mathrm{CRA}$.
We will define and use these identifications in Appendix A.2.

######  Proposition 2.8 ([1]).

There is a bijection between $\mathrm{WA}$ and linear $\mathrm{CRA}$ with a
single state.

Given a $\mathrm{WA}$, one can build an equivalent $\mathrm{CRA}$ with as many
registers as states of the $\mathrm{WA}$: for each letter $a$, the transition
matrix $\mu(a)$ can be interpreted as a (linear) substitution, associated with
the self-loop of label $a$. The converse easily follows from the previous
observations when the $\mathrm{CRA}$ has a single state.

######  Example 2.9 (Example 2.2 continued).

The $\mathrm{CRA}$ depicted on the left of Figure 2 is obtained by the
translation of the $\mathrm{WA}$ of Figure 1 into $\mathrm{CRA}$ with a single
state.

######  Remark 2.10.

Sequential $\mathrm{WA}$ are exactly linear $\mathrm{CRA}$ with a single
register.

Indeed, both sequential $\mathrm{WA}$ and linear $\mathrm{CRA}$ with only one
register are deterministic finite automata that can also store a single value
updated at each transition using only products. They can then be identified.

##  3 Problems and Main Results

######  Definition 3.1 (Register minimization problem).

Given a class $\mathcal{C}$ of $\mathrm{CRA}$, we ask:

  * •

Input: a rational series $f$ realized by a given $\mathrm{WA}$, and an integer
$k\in\mathbb{N}$

  * •

Question: Does there exist a $\mathrm{CRA}$ realizing $f$ in the class
$\mathcal{C}$ with at most $k$ registers?

We will show this problem is decidable for the classes of linear and affine
$\mathrm{CRA}$:

######  Theorem 3.2.

The register minimization problem is decidable for the classes of linear and
affine $\mathrm{CRA}$ in 2-ExpTime. Furthermore, the algorithm exhibits a
solution when it exists.

For a rational series $f$, the minimal number of registers needed to realize
$f$ using $\mathrm{CRA}$ in some class $\mathcal{C}$ is called its _register
complexity with respect to class $\mathcal{C}$_. Dually, if one wants to
minimize the number of states, then we know we can always build a linear
(hence affine) $\mathrm{CRA}$ with a single state (Proposition 2.8). A more
ambitious goal is to try to reduce simultaneously the number of states and of
registers, in some given class $\mathcal{C}$ of $\mathrm{CRA}$. Observe that,
in general, there is no $\mathrm{CRA}$ with minimal numbers of both states and
registers (see Example 2.5). Given a rational series $f$, we say that a pair
$(n,k)$ is _optimal_ if $f$ can be realized by a $\mathrm{CRA}$ in class
$\mathcal{C}$ with $n$ states and $k$ registers and no $\mathrm{CRA}$ of
$\mathcal{C}$ realizing $f$ with at most $n$ states can have strictly less
than $k$ registers and vice-versa.

Formally, we call the _state-register complexity with respect to class
$\mathcal{C}$_ of a rational series $f$, the set of optimal pairs of integers
$(n,k)$.

This leads to the definition of a second minimization problem:

######  Definition 3.3 (State-Register minimization problem).

Given a class $\mathcal{C}$ of $\mathrm{CRA}$, we ask:

  * •

Input: a rational series $f$ realized by a given $\mathrm{WA}$, and two
integers $n,k\in\mathbb{N}$

  * •

Question: Does there exist a $\mathrm{CRA}$ realizing $f$ in the class
$\mathcal{C}$ with at most $n$ states and at most $k$ registers?

In the sequel, we solve this problem for linear and affine $\mathrm{CRA}$:

######  Theorem 3.4.

The state-register minimization problem is decidable for the classes of linear
and affine $\mathrm{CRA}$ in NExpTime. Furthermore, the algorithm exhibits a
solution when it exists.

######  Remark 3.5.

The complexities we give are valid for fields where it is possible to perform
elementary operations efficiently (e.g. $\mathbb{Q}$). See Remark 5.9 for a
more detailed discussion on the matter.

##  4 Characterizing the state-register complexity using invariants of WA

###  4.1 Zariski topologies and invariants of WA

Let $\mathbb{K}$ be a field and $n\in\mathbb{N}$. The _Zariski topology_ on
$\mathbb{K}^{n}$ is defined as the topology whose closed sets are the sets of
common roots of a finite collection of polynomials of
$\mathbb{K}[X_{1},\dots,X_{n}]$. A linear version of this topology, called the
_linear Zariski topology_ , was introduced by Bell and Smertnig in [3]. Its
closed sets, which we will call _Z-linear sets_ , are finite unions of vector
subspaces of $\mathbb{K}^{n}$.

A set $S\subseteq\mathbb{K}^{n}$ is called _irreducible_ if, for all closed
sets $C_{1}$ and $C_{2}$, such that $S\subseteq C_{1}\cup C_{2}$, we have
either $S\subseteq C_{1}$ or $S\subseteq C_{2}$. The Zariski topologies
defined above are Noetherian topologies in which every closed set can be
written as a finite union of irreducible components. We then define the
_dimension_ of a Z-linear set as the maximum dimension of its irreducible
components and their number will be called its _length_.

For a set $S\subseteq\mathbb{K}^{n}$, $\overline{S}^{\ell}$ will denote its
closure in the linear Zariski topology. In this topology, closed irreducible
sets are vector subspaces of $\mathbb{K}^{n}$ and linear maps are continuous
and closed maps (mapping closed sets to closed sets). In particular, for all
$S\subseteq\mathbb{K}^{n}$ and linear map
$f:\mathbb{K}^{n}\to\mathbb{K}^{n}$,$\overline{f(S)}^{\ell}=f(\overline{S}^{\ell})$.
Moreover, if $S\subseteq\mathbb{K}^{n}$ is irreducible and
$f:\mathbb{K}^{n}\to\mathbb{K}^{n}$ is continuous, then $f(S)$ is irreducible.
These properties will be used implicitly in the following (see [3, Lemma 3.5]
for more details and references).

We will also define an affine version of this topology that enjoy the same
properties in Subsection 4.4.

######  Definition 4.1.

Let $\Sigma$ be a finite alphabet and let $\mathcal{R}=(u,\mu,v)$ be a
$d$-dimensional $\mathrm{WA}$ on $\Sigma$ over $\mathbb{K}$. A subset
$I\subseteq\mathbb{K}^{d}$ is called an _invariant_ of $\mathcal{R}$ if $u\in
I$ and, for all $w\in I$ and $a\in\Sigma$, $w\mu(a)\in I$. For two invariants
$I_{1}$ and $I_{2}$, we say that $I_{1}$ is _stronger_ than $I_{2}$ if
$I_{1}\subseteq I_{2}$. In particular, the strongest invariant of
$\mathcal{R}$ is its _reachability set_
$\textup{{LR}}\left(\mathcal{R}\right)=u\mu(\Sigma^{*})$.

An invariant that is also a Z-linear set will be called a _Z-linear_
invariant. The strongest Z-linear invariant of $\mathcal{R}$ is the closure of
$\textup{{LR}}\left(\mathcal{R}\right)$ in the linear Zariski topology (which
is well-defined since the topology is Noetherian).

######  Example 4.2 (Example 2.2 continued).

The reachability set of the $\mathrm{WA}$ considered in Example 2.2 is
$\textup{{LR}}\left(\mathcal{R}\right)=\big{\\{}(2^{2n},0)\,\big{|}\,\allowbreak
n\in\mathbb{N}\big{\\}}\cup\left\\{(0,2^{2n+1})\,\middle|\,n\in\mathbb{N}\right\\}$.
Its strongest Z-linear invariant is then the union of the two coordinate axes
of the plane
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}=\textup{{span}}\left(1,0\right)\cup\textup{{span}}\left(0,1\right)$.

Indeed, the inclusion $\subseteq$ comes from the fact that
$u=(1,0)\in\textup{{span}}\left(1,0\right)$ and
$\textup{{span}}\left(1,0\right)\cup\textup{{span}}\left(0,1\right)$ is stable
by multiplication by $\mu(a)$ and the inclusion $\supseteq$ comes from the
fact that, for the linear Zariski topology, $\left\\{(1,0)\right\\}$ is dense
in $\textup{{span}}\left(1,0\right)$ and $\left\\{(0,2)\right\\}$ is dense in
$\textup{{span}}\left(0,1\right)$.

######  Remark 4.3.

In the previous example, the strongest Z-linear invariant is actually the
strongest algebraic invariant (_i.e._ closed in the Zariski topology). Of
course, this is not always the case.

The Z-linear invariants of two $\mathrm{WA}$ realizing the same function do
not necessarily coincide but, since $\mathbb{K}$ is a field, it is well-known
that for every rational series $f$, there exists a (computable) minimal
$\mathrm{WA}$ realizing $f$ that is unique up to similarity in the following
sense (see [15, Proposition 4.10 (Chapter III)]):

######  Definition 4.4.

Let $\mathcal{R}=(u,\mu,v)$ and
$\mathcal{R}^{\prime}=(u^{\prime},\mu^{\prime},v^{\prime})$ be two
$d$-dimensional $\mathrm{WA}$ over $\mathbb{K}$.

$\mathcal{R}$ and $\mathcal{R}^{\prime}$ are said to be _similar_ if there
exists an invertible (change of basis) matrix $P\in\mathbb{K}^{d\times d}$
such that $u^{\prime}=uP$, $\mu^{\prime}(a)=P^{-1}\mu(a)P$ for all
$a\in\Sigma$ and $v^{\prime}=P^{-1}v$.

######  Remark 4.5.

The Z-linear invariants of two similar $\mathrm{WA}$ $\mathcal{R}$ and
$\mathcal{R}^{\prime}$ only differ by a change of basis. i.e. there is a
bijection between the Z-linear invariants of $\mathcal{R}$ and those of
$\mathcal{R}^{\prime}$ that, in particular, preserves the length and
dimension.

###  4.2 Strongest invariants and characterization

The notion of strongest Z-linear invariant was introduced by Bell and Smertnig
in [3], under the name “linear hull”. They showed, in [4], that it is
computable and can be used to decide whether a $\mathrm{WA}$ is equivalent to
a deterministic (or an unambiguous) one.

######  Theorem 4.6 ([3, Theorem 1.3]).

A rational series $f$ can be realized by a sequential $\mathrm{WA}$ iff the
strongest Z-linear invariant of a minimal $\mathrm{WA}$ realizing $f$ has
dimension at most 1.

The following result generalizes this theorem by linking linear $\mathrm{CRA}$
to Z-linear invariants. It constitutes the key characterization that will
allow us to solve the minimization problems.

######  Theorem 4.7 (Characterization).

Let $f$ be a rational series. Then $f$ can be realized by a linear
$\mathrm{CRA}$ with $n$ states and $k$ registers iff there exists a minimal
$\mathrm{WA}$ realizing $f$ that has a Z-linear invariant of length at most
$n$ and dimension at most $k$.

As we will see in Subsection 4.4, this theorem can also be extended to affine
$\mathrm{CRA}$.

Observe that, thanks to Remark 4.5, the property of the above characterization
is actually valid for _every_ minimal $\mathrm{WA}$ realizing $f$. Moreover,
since the dimension of the strongest Z-linear invariant is minimal, finding
this dimension allows to solve the register minimization problem for linear
$\mathrm{CRA}$. This is formalized in the following result, which generalizes
Theorem 4.6 thanks to Remark 2.10.

######  Corollary 4.8.

The register complexity of a rational series $f$ w.r.t. the class of linear
$\mathrm{CRA}$ is the dimension of the strongest Z-linear invariant of any
minimal $\mathrm{WA}$ realizing $f$.

An immediate consequence of this result is that computing the strongest
invariant allows to decide the register minimization problem.

######  Example 4.9 (Example 2.2 continued).

As we have seen in Example 4.2,
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}$ is 1-dimensional and
has two irreducible components, thus $\llbracket\mathcal{R}\rrbracket$ can be
realized by a $\mathrm{CRA}$ with two states and one register (depicted on the
right of Figure 2).

###  4.3 Invariants of minimal WA and correspondence with CRA

######  Proposition 4.10.

Let $\mathcal{R}$ be a $\mathrm{WA}$ realizing a rational series $f$. If
$\mathcal{R}$ has a Z-linear invariant of length $n$ and dimension $k$, then
every minimal $\mathrm{WA}$ realizing $f$ has a Z-linear invariant of length
$\leq n$ and dimension $\leq k$.

Thanks to Remark 4.5, it suffices to show the existence of one minimal
$\mathrm{WA}$ verifying the proposition, since they are all similar. It is
known (see Proposition 2.3) that a minimal $\mathrm{WA}$ can be obtained from
a $\mathrm{WA}$ by alternating between two constructions which reduce the
dimension to make it match the one of the span of the left (resp. right)
reachability set. The result then follows from the next lemma, which states
that both constructions decrease the length and dimension of the invariants.
We prove it by considering an adequate change of basis, and verifying that it
preserves invariants.

######  Lemma 4.11.

Let $\mathcal{R}$ be a $\mathrm{WA}$ realizing a rational series $f$, let
$S_{\mathcal{R}}$ be a Z-linear invariant of $\mathcal{R}$ of length $n$ and
dimension $k$ and let
$r=\dim(\textup{{span}}\left(\textup{{LR}}\left(\mathcal{R}\right)\right))$.
We can construct an $r$-dimensional $\mathrm{WA}$ $\mathcal{R}^{\prime}$
realizing $f$, with a Z-linear invariant $S_{\mathcal{R}^{\prime}}$ of length
$\leq n$ and dimension $\leq k$. The same holds with
$r=\dim(\textup{{span}}\left(\textup{{RR}}\left(\mathcal{R}\right)\right))$.

The next proposition allows to go from Z-linear invariants of $\mathrm{WA}$ to
$\mathrm{CRA}$. This construction builds on the one of [3, Lemma 3.13], in
which they build an equivalent $\mathrm{WA}$ from the strongest Z-linear
invariant of a $\mathrm{WA}$. We show that an analogous construction is valid
for any Z-linear invariant, and that we can use states of $\mathrm{CRA}$ to
represent the different irreducible components of the invariant, thus reducing
the number of registers used to the dimension of the invariant.

######  Proposition 4.12.

Let $\mathcal{R}$ be a $\mathrm{WA}$. If $\mathcal{R}$ has a Z-linear
invariant of length $n$ and dimension $k$, then there exists a linear
$\mathrm{CRA}$ $\mathcal{A}$, with $n$ states and $k$ registers, such that
$\llbracket\mathcal{A}\rrbracket=\llbracket\mathcal{R}\rrbracket$.

The next proposition shows the converse direction, from $\mathrm{CRA}$ to
invariants of $\mathrm{WA}$. The construction is the classical one from
$\mathrm{CRA}$ to $\mathrm{WA}$. The existence of the adequate invariant
follows from the determinism of the $\mathrm{CRA}$ which ensures that in any
reachable configuration, only coordinates associated with the reachable state
of the $\mathrm{CRA}$ can be non-zero.

######  Proposition 4.13.

Let $\mathcal{A}$ be a linear $\mathrm{CRA}$. If $\mathcal{A}$ has $n$ states
and $k$ registers, then there exists a $\mathrm{WA}$ $\mathcal{R}$, with a
Z-linear invariant of length $n$ and dimension $k$, such that
$\llbracket\mathcal{A}\rrbracket=\llbracket\mathcal{R}\rrbracket$.

Using the three previous propositions, we can finally prove the main
characterization:

######  Proof 4.14 (Proof of Theorem 4.7).

Given a linear $\mathrm{CRA}$ with $n$ states and $k$ registers, we can
construct, thanks to Proposition 4.13, an equivalent $\mathrm{WA}$ with a
Z-linear invariant of length $n$ and dimension $k$. Then the desired minimal
$\mathrm{WA}$ exists thanks to Proposition 4.10.

Reciprocally, applying the construction of Proposition 4.12 to any minimal
$\mathrm{WA}$ gives the desired linear $\mathrm{CRA}$.

As we will discuss in the next subsection below, the three propositions we
used for this proof can also be adapted to yield the same result for affine
$\mathrm{CRA}$.

###  4.4 Z-affine invariants and affine CRA

All the results of Section 4 can actually be extended to affine $\mathrm{CRA}$
using the _affine Zariski topology_ instead of the linear one. It is a slight
generalization of the linear Zariski topology where closed sets, called _Z-
affine_ sets, are finite unions of affine spaces instead of vector spaces,
with lengths and dimensions defined like in the linear case. It is still a
Noetherian topology coarser than the Zariski topology, affine maps are
continuous and closed maps in this topology and, more broadly, it enjoys the
same properties as the linear Zariski topology we considered throughout this
section. For a set $S\subseteq\mathbb{K}^{n}$, we will denote by
$\overline{S}^{a}$ it closure in the affine Zariski topology and, similarly to
the linear case, for a $\mathrm{WA}$ $\mathcal{R}=(u,\mu,v)$, we will call any
invariant of $\mathcal{R}$ that is a Z-affine set a _Z-affine invariant_ of
$\mathcal{R}$. Of course, the strongest Z-affine invariant of $\mathcal{R}$ is
still the closure of its reachability set i.e. its “affine hull”
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{a}$ and Remark 4.5 is still
true for Z-affine invariants.

We obtain the same characterization of Theorem 4.7 in the affine setting :

######  Theorem 4.15 (Characterization).

Let $f$ be a rational series. Then $f$ can be realized by an affine
$\mathrm{CRA}$ with $n$ states and $k$ registers iff there exists a minimal
$\mathrm{WA}$ realizing $f$ that has a Z-affine invariant of length at most
$n$ and dimension at most $k$.

We can show that Propositions 4.10, 4.12 and 4.13 are also true if we replace
Z-linear invariants by Z-affine ones and linear $\mathrm{CRA}$ by affine ones.
So, the proof of Theorem 4.15 remains the same as Theorem 4.7. All the details
can be found in Appendix A.2.

Of course, this theorem has the same consequences of its linear counterpart
and we obtain an affine version of Corollary 4.8

######  Corollary 4.16.

The register complexity of a rational series $f$ w.r.t. the class of affine
$\mathrm{CRA}$ is the dimension of the strongest Z-affine invariant of any
minimal $\mathrm{WA}$ realizing $f$.

Working in the affine Zariski topology instead of the linear one can decrease
the dimension of the strongest invariant by one, as shown in the following
example.

######  Example 4.17.

On the alphabet $\Sigma=\left\\{a\right\\}$, let $\mathcal{R}=(u,\mu,v)$,
where $u=(1,2)$, $\mu(a)=\begin{pmatrix}1&0\\\ 1&2\end{pmatrix}$ and
$v=(1,0)^{t}$, be a $\mathrm{WA}$ (over $\mathbb{R}$) realizing the rational
series $f$ defined by $f(a^{n})=\sum_{i=0}^{n}2^{i}=2^{n+1}-1$.

The reachability set of $\mathcal{R}$ is
$\textup{{LR}}\left(\mathcal{R}\right)=\big{\\{}\left(\sum_{i=0}^{n}2^{i},2^{n+1}\right)\,\big{|}\,n\in\mathbb{N}\big{\\}}$.

For the linear Zariski topology, $\textup{{LR}}\left(\mathcal{R}\right)$ is
dense in $\mathbb{R}^{2}$. So the strongest Z-linear invariant
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}=\mathbb{R}^{2}$ is
two-dimensional. However, note that, for all
$(x,y)\in\textup{{LR}}\left(\mathcal{R}\right)$, $y=x+1$. So, by an argument
of density in the affine Zariski topology, the strongest Z-affine invariant
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{a}$ is the affine line
$y=x+1$, which is one-dimensional.

Thus, in the case where the dimensions of the affine and linear hulls doesn’t
match, using affine $\mathrm{CRA}$ instead of linear $\mathrm{CRA}$ can allow
to save one register :

######  Example 4.18 (Example 4.17 continued).

The two $\mathrm{CRA}$ depicted on Figure 3 both realize the function of
Example 4.17. On the left we have a linear $\mathrm{CRA}$ with two registers
and, on the right, an affine $\mathrm{CRA}$ with only one register. The
characterization theorems show that both have the minimal number of registers
for their respective classes of $\mathrm{CRA}$.

$\left\\{\begin{aligned} X\coloneqq 1\\\ Y\coloneqq
2\end{aligned}\right.$$X$$a:\left\\{\begin{aligned} &X\coloneqq X+Y\\\
&Y\coloneqq Y*2\end{aligned}\right.$

$X\coloneqq 2$$X-1$$a:X\coloneqq X*2$

Figure 3: Two CRA detailed in Example 4.18.

##  5 Algorithms and complexity for the minimization problems

We present two original algorithms to solve the minimization problems we
consider. It is worth observing the difference between the two
characterizations we have obtained: while the register complexity can be
computed from a canonical object (the strongest Z-linear invariant of the
$\mathrm{WA}$), the state-register complexity is based on the existence of a
particular Z-linear invariant. This explains why we derive a non-deterministic
procedure for the latter, and a deterministic for the former.

###  5.1 Algorithm for the state-register minimization problem

We provide here a NExpTime algorithm for the state-register minimization
problem, hence proving Theorem 3.4. The algorithm runs in NPTime in $n$, $k$,
and the size of the automaton. The fact that $n$ is given in binary explains
the exponential discrepancy.

Small representations of Z-affine sets Let $\mathcal{R}=(u,\mu,v)$ be a
$\mathrm{WA}$ of dimension $d$ over an alphabet $\Sigma$. Let
$L=A_{1}\cup\cdots\cup A_{n}$ be a Z-affine set of length $n$ of
$\mathbb{K}^{d}$.

An $\mathcal{R}$-representation $R$ of $L$ is a set of $n$ finite sets of
words $S_{1},\ldots,S_{n}$ such that $\textup{{aff}}\left(\left\\{u\mu(w)|\
w\in S_{i}\right\\}\right)=A_{i}$ for all $i\in\left\\{1,\cdots,n\right\\}$.
The _size_ of $R$ is the sum of the lengths of all words appearing in $R$. The
following key lemma shows that all Z-affine invariants of $\mathcal{R}$ have
small $\mathcal{R}$-representations, up to considering stronger invariants.

######  Lemma 5.1.

Let $\mathcal{R}$ be a $\mathrm{WA}$. Let $I$ be a Z-affine invariant of
$\mathcal{R}$ of length $n$ and dimension $k$. There exists an
$\mathcal{R}$-representation $R$ of size $\leq n^{2}k^{2}$ of a Z-affine
invariant $J\subseteq I$, of dimension $\leq k$ and length $\leq n$.

This property allows to derive the non-deterministic algorithm. First,
minimization of a $\mathrm{WA}$ over a field can be performed in polynomial
time (see e.g.  [15, Corollary 4.17]). Then, let $\mathcal{R}$ be a minimal
$\mathrm{WA}$ and let $k,n$ be positive integers. From Lemma 5.1, we know that
a Z-affine invariant of dimension $k$ and length $n$ can be represented in
size $O(k^{2}n^{2})$ (up to finding a stronger invariant with smaller
dimension and length). The algorithm works thusly: first step is to guess an
$\mathcal{R}$-representation $R$ of a Z-affine set. The second step is to
check that $R$ represents an invariant, which can be done easily using basic
linear algebra. From this one can compute an affine $\mathrm{CRA}$ with $k$
registers and $n$ states. Moreover, if we require that $R$ is Z-linear, we
obtain a linear $\mathrm{CRA}$. If $R$ is not an invariant, the computation
rejects. Note that different accepting computations may give rise to different
invariants and thus different CRAs.

###  5.2 Algorithm for the computation of Z-affine invariants

We describe a deterministic procedure which, given a $\mathrm{WA}$
$\mathcal{R}$ and an integer $c$, returns a Z-affine invariant $J$ which is
stronger that any Z-affine invariant $I$ of $\mathcal{R}$ of length at most
$c$. When $c$ is chosen large enough, this procedure returns the strongest
Z-affine invariant of $\mathcal{R}$. A similar procedure works as well for the
computation of Z-linear invariants.

Algorithm 1 Computing a Z-affine invariant

1:A $\mathrm{WA}$ $\mathcal{R}=(u,\mu,v)$ of dimension $d$, an integer $c$

2:A Z-affine invariant $J$ of $\mathcal{R}$ stronger than $I_{c}(\mathcal{R})$

3:$J\coloneqq\\{u\\}$

4:while $J$ is not an invariant of $\mathcal{R}$ do

5: Pick some component $A$ of $J$, and some matrix $M$ of $\mathcal{R}$ s.t.
$A\cdot M\not\subseteq J$

6: $J\coloneqq J\cup A\cdot M$

7: if $\mathrm{length}(J)>c^{d}$ then

8: $J\coloneqq\textsc{reduce}(J)$

9: end if

10:end while

11:return $J$

Intuitively, this procedure will build a Z-affine set $J$ as follows: it
starts with a set containing only the initial vector of $\mathcal{R}$, and
incrementally extends it until it forms an invariant. During this process, it
should ensure that $J$ is included in every Z-affine invariant $I$ of
$\mathcal{R}$ of length at most $c$. This relies on the following easy
observation: if such an invariant $I$ contains at least $c+1$ points on the
same affine line (_i.e._ a 1-dimensional affine space, denoted $D$), then $I$
must have a component that contains $D$. Indeed, as $I$ has length at most
$c$, one of its components contains two such points. As this component is
irreducible, it is an affine subspace, hence contains $D$. This reasoning can
be lifted to higher dimensions as follows.

Given a $\mathrm{WA}$ $\mathcal{R}$, and $c\in\mathbb{N}$, we denote by
$I_{c}(\mathcal{R})=\bigcap_{\mathrm{length}(I)\leq c}I$ the intersection of
all Z-affine invariants of $\mathcal{R}$ with at most $c$ components.

######  Lemma 5.2.

Let $\mathcal{R}$ be a $\mathrm{WA}$ and let $c,k\in\mathbb{N}$. Let
$A_{1},\ldots,A_{c^{k}+1}\subseteq I_{c}(\mathcal{R})$ be affine spaces such
that: for any $P\subseteq\llbracket 1,c^{k}+1\rrbracket$ with $|P|\geq
c^{k-1}+1$, $\textup{{aff}}\left(\cup_{i\in P}A_{i}\right)$ has dimension $k$.
Then $\textup{{aff}}\left(\cup_{i\in\llbracket
1,c^{k}+1\rrbracket}A_{i}\right)\subseteq I_{c}(\mathcal{R})$.

Using this lemma, we derive an effective procedure to simplify a Z-affine set
$J=A_{1}\cup\cdots\cup A_{c^{d}+1}$ by “merging” two components. We denote by
$\textsc{reduce}(J)$ the resulting set.

######  Claim 1.

Let $\mathcal{R}=(u,\mu,v)$ be a $\mathrm{WA}$ of dimension $d$, let
$c\in\mathbb{N}$. Let $A_{1},\ldots,A_{c^{d}+1}\subseteq I_{c}(\mathcal{R})$
be affine spaces. One can find $1\leq i<j\leq c^{d}+1$ such that
$\textup{{aff}}\left(A_{i}\cup A_{j}\right)\subseteq I_{c}(\mathcal{R})$, in
time $O(c^{p(d)})$, for some fixed polynomial $p$.

######  Theorem 5.3.

Algorithm 1 is correct and terminates in time $O(c^{p(d)})$.

######  Proof 5.4.

Let us first discuss termination. Because of line $5$-$7$, the length of $J$
is at most $c^{d}+1$. Moreover $J$ is an increasing Z-affine set, thus its
value can be modified at most $(d+1)\cdot(c^{d}+1)$ times, thus from Claim 1
the algorithm terminates in time $O(c^{p(d)})$.

We now discuss correctness. We need to show that $J$ is stronger than
$I_{c}(\mathcal{R})$. Initially, this holds. Moreover, if $A\subseteq
I_{c}(\mathcal{R})$ is an affine set, then for any $M\in\mu(\Sigma$)$,A\cdot
M\subseteq I_{c}(\mathcal{R})$, since $I_{c}(\mathcal{R})$ is invariant. Thus,
line $4$ preserves the property that $J$ is stronger than
$I_{c}(\mathcal{R})$. Using Claim 1, the Reduce subroutine also preserves this
property, since it only merges components whose affine span is contained in
$I_{c}(\mathcal{R})$.

###  5.3 Complexity of the register minimization problem

In order to compute the strongest Z-linear and Z-affine invariants of a
$\mathrm{WA}$ using Algorithms 1, it is sufficient to be able to bound their
lengths. The following result gives such bounds.

######  Theorem 5.5.

Let $\mathcal{R}=(u,\mu,v)$ be a $d$-dimensional $\mathrm{WA}$ on a finite
alphabet $\Sigma$. We have the following upper bounds :

  * •

The lengths of $\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}$ and
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{a}$ are at most doubly-
exponential in $d$.

  * •

If $\left<\mu(\Sigma)\right>$ is commutative (_e.g._ $\Sigma$ is unary), then
the length of $\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}$ is at
most exponential in $d$.

We also have the following lower bound (which also hold for $\mathrm{WA}$ over
a unary alphabet):

  * •

For all $d>0$, there exist a $d$-dimensional $\mathrm{WA}$ having strongest
Z-linear and Z-affine invariants with lengths exponential in $d$.

######  Proof 5.6 (Proof sketch).

The first item is shown in [4], where the authors sketch a proof of a double-
exponential upper bound on the length of the strongest Z-linear invariant of a
$\mathrm{WA}$, using tools from algebraic geometry, which holds for
$\mathbb{Q}$ in particular and for any field $\mathbb{K}$ where there is a
double-exponential bound on the maximal order of finite groups of invertible
matrices (see [4, Proposition 48 and Remark 41]). Their proof can be adapted
to $\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{a}$. The proof of the
second item relies on basic linear algebra and on results and ideas from [4]
for invertible matrices (see [4, Lemma 13 and Theorem 10]). Last, the lower
bound is shown using a family of $\mathrm{WA}$
$(\mathcal{R}_{i})_{i\in\mathbb{N}}$ whose dimension is polynomial in $i$ and
strongest Z-linear invariant has a length that is exponential in $i$. It is
defined, using permutation matrices of dimension $p$, for some prime number
$p$, which generate cyclic groups. The family is obtained by using block
matrices composed of such permutation matrices. All the details are given in
Appendix B.4.

Thanks to this theorem, using Algorithm 1 with a large enough $c$ (at most
doubly-exponential in the dimension of the given $\mathrm{WA}$), and thanks to
Theorem 5.3, we can prove the following result:

######  Theorem 5.7.

The strongest Z-linear/affine invariant of a $\mathrm{WA}$ is computable in
2-ExpTime.

This allows us to prove Theorem 3.2. Indeed, given a $\mathrm{WA}$
$\mathcal{R}$, we first compute an equivalent minimal $\mathrm{WA}$, which can
be done in polynomial time (see e.g.  [15, Corollary 4.17]). Then, using
Algorithm 1, we compute the strongest Z-linear (resp. Z-affine) invariant of
$\mathcal{R}$. Corollary 4.8 (resp. Corollary 4.16) ensures that its dimension
is the register complexity of $f$ w.r.t. the class of linear (resp. affine)
$\mathrm{CRA}$, and the effectiveness follows from Proposition 4.12 (resp. its
affine version).

Moreover, thanks to Theorem 5.7 and the results of [3], we also have:

######  Theorem 5.8.

The sequentiality and unambiguity of a rational series are in 2-ExpTime.

Note that the complexities of the last two theorems drop down to ExpTime when
we have a simply exponential bound on the length of the strongest invariant.
This is the case when one considers unary alphabets or $\mathrm{WA}$ with
commuting transition matrices in the linear setting, as stated in Theorem 5.5.
In these cases, the bound is sharp. It is still not clear however whether it
is possible to close the gap between the bounds in the general case.

######  Remark 5.9.

It is also worth noting that, while the characterizations that we obtained are
valid for any field, the complexities of the algorithms are given in terms of
number of elementary operations over the considered field. Which means that
they hold for fields where we can perform basic operations in polynomial time
(such as $\mathbb{Q}$ or its finite extensions). Moreover, the general upper
bounds on the lengths given by Theorem 5.5 were proven only for fields
verifying a specific property (which is verified by $\mathbb{Q}$). See the
proof for more details.

###  5.4 State/register tradeoff

Reducing the number of registers may increase the number of states and vice-
versa. The following theorem summarizes what we know on this tradeoff.

######  Theorem 5.10.

Let $f$ be a rational series realized by some $d$-dimensional $\mathrm{WA}$
$\mathcal{R}$. Consider some pair of integers $(n,k)$ optimal for $f$ w.r.t.
the class of linear $\mathrm{CRA}$. The inequalities $1\leq
n\leq\mathrm{length}(\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell})=O(2^{2^{d}})$
and $\dim(\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell})\leq k\leq
d$ hold true.

(They are valid in the affine setting as well)

######  Remark 5.11.

Building the $\mathrm{CRA}$ from the strongest invariant is not always
optimal. There are some cases where it is possible to reduce the number of
states of a $\mathrm{CRA}$ exponentially, while keeping the minimal number of
registers, by choosing an invariant that is weaker than the strongest
Z-linear/Z-affine invariant but shorter.

##  6 Conclusion

We have shown how to decide variants of $\mathrm{CRA}$ minimization problems,
and have given complexity for the respective algorithms. There are several
ways in which these algorithms could be improved. First, it would be worth
reducing the gap between the lower and the upper bounds on the length of the
strongest Z-linear invariant. Second, identifying a canonical invariant
associated with the state-register minimization problem would allow to derive
a deterministic algorithm for this problem. Third, one could hope for better
complexity if one only considers the existence of equivalent CRA. For
instance, in [12] the authors give a PSpace algorithm for the determinization
problem (i.e. $1$-register minimization problem) in the case of a polynomially
ambiguous automaton, via a quite different approach.

Another line of research consists in trying to use the techniques we developed
to solve the register minimization problem for other classes of
$\mathrm{CRA}$, for instance copyless $\mathrm{CRA}$ (which correspond to
multi-sequential $\mathrm{WA}$). Another ambitious goal is to consider
register minimization in the context of different semirings, but there all the
linear algebra tools which are crucial to solving these problems completely
break down. Similarly, it seems that register minimization for polynomial
automata would be very difficult: it was shown recently in [11] that the
strongest algebraic invariant of a polynomial automaton is not computable. One
possibility may be to bound the “degree” of the invariants, where Z-affine
sets would correspond to algebraic sets of degree one.

## References

  * [1] Rajeev Alur, Loris D’Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan.  Regular functions and cost register automata.  In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pages 13–22. IEEE Computer Society, 2013.
  * [2] Rajeev Alur and Mukund Raghothaman.  Decision problems for additive regular functions.  In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, volume 7966 of Lecture Notes in Computer Science, pages 37–48. Springer, 2013.
  * [3] Jason Bell and Daniel Smertnig.  Noncommutative rational pólya series.  Selecta Mathematica, 27, 07 2021.  doi:10.1007/s00029-021-00629-2.
  * [4] Jason P. Bell and Daniel Smertnig.  Computing the linear hull: Deciding deterministic? and unambiguous? for weighted automata over fields.  In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023, pages 1–13. IEEE, 2023.  doi:10.1109/LICS56636.2023.10175691.
  * [5] Jean Berstel.  Transductions and context-free languages, volume 38 of Teubner Studienbücher : Informatik.  Teubner, 1979.  URL: https://www.worldcat.org/oclc/06364613.
  * [6] Christian Choffrut.  Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles.  Theor. Comput. Sci., 5(3):325–337, 1977.  URL: http://dx.doi.org/10.1016/0304-3975(77)90049-4, doi:10.1016/0304-3975(77)90049-4.
  * [7] Thomas Colcombet and Daniela Petrisan.  Automata in the category of glued vector spaces.  In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, volume 83 of LIPIcs, pages 52:1–52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.MFCS.2017.52.
  * [8] Laure Daviaud.  Containment and equivalence of weighted automata: Probabilistic and max-plus cases.  In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications \- 14th International Conference, LATA 2020, Milan, Italy, March 4-6, 2020, Proceedings, volume 12038 of Lecture Notes in Computer Science, pages 17–32. Springer, 2020.  doi:10.1007/978-3-030-40608-0_2.
  * [9] Laure Daviaud, Ismaël Jecker, Pierre-Alain Reynier, and Didier Villevalois.  Degree of sequentiality of weighted automata.  In FOSSACS 2017, volume 10203 of Lecture Notes in Computer Science, pages 215–230, 2017.
  * [10] Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot.  A generalised twinning property for minimisation of cost register automata.  In LICS ’16, pages 857–866. ACM, 2016.
  * [11] Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell.  On strongest algebraic program invariants.  J. ACM, 70(5):29:1–29:22, 2023.  doi:10.1145/3614319.
  * [12] Ismaël Jecker, Filip Mazowiecki, and David Purser.  Determinisation and unambiguisation of polynomially-ambiguous rational weighted automata.  In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, July 8-11, 2024, pages 46:1–46:13. ACM, 2024.  doi:10.1145/3661814.3662073.
  * [13] Heiko Vogler Manfred Droste, Werner Kuich.  Handbook of Weighted Automata.  Springer Berlin, Heidelberg, 2009.  doi:10.1007/978-3-642-01492-5.
  * [14] Mehryar Mohri.  Finite-state transducers in language and speech processing.  Comput. Linguistics, 23(2):269–311, 1997.
  * [15] Jacques Sakarovitch.  Elements of Automata Theory.  Cambridge University Press, 2009.  doi:10.1017/CBO9781139195218.
  * [16] Marcel Paul Schützenberger.  On the definition of a family of automata.  Inf. Control., 4(2-3):245–270, 1961.  doi:10.1016/S0019-9958(61)80020-X.

##  Appendix A Complements to Section 4

###  A.1 Examples of Subsection 4.1

Complement to Remark 4.3

Consider a $\mathrm{WA}$ over a one-letter alphabet $\\{a\\}$ with $u=(1,1)$
and $\mu(a)=\begin{pmatrix}2&0\\\ 0&4\end{pmatrix}$. One can verify that the
strongest algebraic invariant is described by a polynomial of degree $2$ (the
second coordinate is the square of the first one), hence is not linear.

Complement to Example 4.17

A graphical representation of the reachability set of the WA described in
Example 4.17 is depicted in Figure 4.

All the reachable vectors are on the affine line $y=x+1$ so the affine hull is
one dimensional but, since the line does not cross the origin, the linear hull
is two dimensional.

Figure 4: Reachability set of the $\mathrm{WA}$ of Example 4.17.

###  A.2 Proofs of the building blocks of Theorem 4.7

We will prove Lemma 4.11 (wich yields Proposition 4.10) and Propositions 4.12
and 4.13 in the affine setting (i.e. using Z-affine sets and affine
$\mathrm{CRA}$) as it is more general, and all the results for the linear
setting follow directly from the constructions of this section.

To simplify dealing with affine $\mathrm{CRA}$, we make the same observations
we made in Section 2 about linear expressions (bringing back the underline
notation to avoid confusion): for a finite set of variables
$\mathcal{X}=\left\\{X_{1},\dots,X_{k}\right\\}$ that we can assume to be
ordered, we identify any affine expression
$e=\sum_{i=1}^{k}\alpha_{i}X_{i}+\beta$ with the affine form
$\underline{e}\colon\mathbb{K}^{k}\to\mathbb{K}$ defined by
$\underline{e}(u)=u\underline{e}^{(l)}+\underline{e}^{(a)}$ with
$\underline{e}^{(l)}=(\alpha_{1},\dots,\alpha_{k})^{t}$ and
$\underline{e}^{(a)}=\beta$. We can then identify any affine substitution
$s\colon\mathcal{X}\to\textup{{Exp}}_{a}(\mathcal{X})$ with the affine map
$\underline{s}\colon\mathbb{K}^{k}\to\mathbb{K}^{k}$ defined by
$\underline{s}(u)=u\underline{s}^{(l)}+\underline{s}^{(a)}$ with
$\underline{s}^{(l)}=(\underline{s(X_{1})}^{(l)}|\cdots|\underline{s(X_{k})}^{(l)})$
and
$\underline{s}^{(a)}=(\underline{s(X_{1})}^{(a)},\cdots,\underline{s(X_{k})}^{(a)})$,
and we can identify any valuation $v\colon\mathcal{X}\to\mathbb{K}$ with the
point $\underline{v}=(v(X_{1}),\cdots,v(X_{k}))$ of the affine space
$\mathbb{K}^{k}$.

We now drop the underline notation and observe that the registers of a linear
(resp. affine) $\mathrm{CRA}$ and their updates can be characterized by the
values of the vector (resp. point) associated with $v_{0}$, and the linear
(resp. affine) maps associated with the $\delta_{\mathcal{X}}(q,a)$ and
$o(q)$, for all $q\in Q$ and $a\in\Sigma$, and we can check that

$\llbracket\mathcal{A}\rrbracket(w)=o(\delta_{Q}(q_{0},w))\left(\delta_{\mathcal{X}}(q_{0},w)\left(v_{0}\,\right)\right)$

####  A.2.1 Proof of Lemma 4.11

In the following, for all $d\in\mathbb{N}$, let
$E_{d}=\left\\{e_{1},\dots,e_{d}\right\\}$ denote the canonical basis of
$\mathbb{K}^{d}$. For two bases $B$ and $B^{\prime}$ of the same vector space,
let $P_{B\to B^{\prime}}$ denote the change of basis matrix from $B$ to
$B^{\prime}$ (whose lines are the coordinates of the vectors of $B^{\prime}$
in the basis $B$). And finally, for two integers $i$ and $j$, let $I_{i}$
denote the identity matrix of size $i$ and let $I_{i\times j}$ denote the $i$
by $j$ matrix $(I_{i}\ |\ 0)$ if $i\leq j$ and $I_{j\times i}^{t}$ otherwise.

######  Claim 2.

If $V$ is an $r$-dimensional vector subspace of $\mathbb{K}^{d}$ and $B$ is a
basis of $\mathbb{K}^{d}$ whose first $r$ vectors form a basis of $V$, then,
for all $v\in V$, since the $d-r$ last entries of the vector $vP_{E_{d}\to B}$
are all zeros, we note that $vP_{E_{d}\to B}I_{d\times r}I_{r\times d}P_{B\to
E_{d}}=v$.

######  Proof A.1 (Proof of Lemma 4.11).

Let us first prove the lemma for the left reachability set. Let
$\mathcal{R}=(u,\mu,v)$, let $d$ be the dimension of $\mathcal{R}$ and let $B$
be a basis of $\mathbb{K}^{1\times d}$ obtained by completing a basis of
$\textup{{span}}\left(\textup{{LR}}\left(\mathcal{R}\right)\right)$ with
arbitrary vectors.

We define $\mathcal{R}^{\prime}$ as $(u^{\prime},\mu^{\prime},v^{\prime})$
where, for all $a\in\Sigma$,

$\displaystyle u^{\prime}=uP_{E_{d}\to B}I_{d\times r}\quad
v^{\prime}=I_{r\times d}P_{B\to E_{d}}v\quad\mu^{\prime}(a)=I_{r\times
d}P_{B\to E_{d}}\mu(a)P_{E_{d}\to B}I_{d\times r}$

We can show by induction, thanks to Claim 2, that
$\textup{{LR}}\left(\mathcal{R}^{\prime}\right)=\textup{{LR}}\left(\mathcal{R}\right)P_{E_{d}\to
B}I_{d\times r}$, and then
$\llbracket\mathcal{R}^{\prime}\rrbracket=\llbracket\mathcal{R}\rrbracket$.

It remains to show that, if $\mathcal{R}$ has a Z-affine invariant
$S_{\mathcal{R}}$ of length $n$ and dimension $k$, then $\mathcal{R}^{\prime}$
has a Z-affine invariant $S_{\mathcal{R}^{\prime}}$ of length $\leq n$ and
dimension $\leq k$. Note that we can assume that
$S_{\mathcal{R}}\subseteq\textup{{span}}\left(\textup{{LR}}\left(\mathcal{R}\right)\right)$,
since
$S_{\mathcal{R}}\cap\textup{{span}}\left(\textup{{LR}}\left(\mathcal{R}\right)\right)$
is also a Z-affine invariant of $\mathcal{R}$, with a length $\leq n$ and a
dimension $\leq k$.

Let us take $S_{\mathcal{R}^{\prime}}=S_{\mathcal{R}}P_{E_{d}\to B}I_{d\times
r}$ and show that it has the right properties. First, it is clear that
$S_{\mathcal{R}^{\prime}}$ is a Z-affine invariant of $\mathcal{R}^{\prime}$,
since $u\in S_{\mathcal{R}}$ then $u^{\prime}=uP_{E_{d}\to B}I_{d\times r}\in
S_{\mathcal{R}^{\prime}}$ and, for all $w^{\prime}\in
S_{\mathcal{R}}^{\prime}$ and $a\in\Sigma$, there exists a $w\in
S_{\mathcal{R}}$ such that $w^{\prime}=wP_{E_{d}\to B}I_{d\times r}$, thus,
since
$S_{\mathcal{R}}\subseteq\textup{{span}}\left(\textup{{LR}}\left(\mathcal{R}\right)\right)$
and thanks to Claim 2:

$\displaystyle w^{\prime}\mu^{\prime}(a)$ $\displaystyle=wP_{E_{d}\to
B}I_{d\times r}I_{r\times d}P_{B\to E_{d}}\mu(a)P_{E_{d}\to B}I_{d\times r}$
$\displaystyle=w\mu(a)P_{E_{d}\to B}I_{d\times r}\in S_{\mathcal{R}}^{\prime}$

and the image of a Z-affine set by a linear map is still a Z-affine set.
Moreover, the irreducible components of $S_{\mathcal{R}^{\prime}}$ are images
of the irreducible components of $S_{\mathcal{R}}$ by a linear map. Thus
$\dim(S_{\mathcal{R}^{\prime}})\leq\dim(S_{\mathcal{R}})$ and
$\textup{{length}}(S_{\mathcal{R}^{\prime}})\leq\textup{{length}}(S_{\mathcal{R}})$.

The case of the right reachability set is proven similarly, using a basis of
$\textup{{span}}\left(\textup{{RR}}\left(\mathcal{R}\right)\right)$. Let $C$
be a basis of $\mathbb{K}^{1\times d}$ obtained by completing a basis of
$\textup{{span}}\left(\textup{{RR}}\left(\mathcal{R}\right)\right)^{t}$ with
arbitrary vectors.

We define $\mathcal{R}^{\prime\prime}$ as
$(u^{\prime\prime},\mu^{\prime\prime},v^{\prime\prime})$ where, for all
$a\in\Sigma$,

$\displaystyle u^{\prime\prime}=uP_{C\to E_{d}}^{t}I_{d\times r}\quad
v^{\prime\prime}=I_{r\times d}P_{E_{d}\to
C}^{t}v\quad\mu^{\prime\prime}(a)=I_{r\times d}P_{E_{d}\to C}^{t}\mu(a)P_{C\to
E_{d}}^{t}I_{d\times r}$

We can show by induction, thanks to Claim 2, that
$\textup{{RR}}\left(\mathcal{R}^{\prime}\right)=I_{r\times d}P_{E_{d}\to
C}^{t}\textup{{RR}}\left(\mathcal{R}\right)$, and then
$\llbracket\mathcal{R}^{\prime}\rrbracket=\llbracket\mathcal{R}\rrbracket$.

Like in the previous case, let $S_{\mathcal{R}}$ be a Z-affine invariant of
$\mathcal{R}$, of length $n$ and dimension $k$ and let
$S_{\mathcal{R}^{\prime\prime}}=S_{\mathcal{R}}P_{C\to E_{d}}^{t}I_{d\times
r}$. Obviously, $u^{\prime\prime}\in S_{\mathcal{R}^{\prime\prime}}$ and, if
$w^{\prime\prime}=wP_{C\to E_{d}}^{t}I_{d\times r}\in
S_{\mathcal{R}^{\prime\prime}}$, then we can show that, for all $a\in\Sigma$,
$w^{\prime\prime}\mu^{\prime\prime}(a)\in S_{\mathcal{R}^{\prime\prime}}$ by
observing that $P_{E_{d}\to C}^{t}\mu(a)P_{C\to E_{d}}^{t}I_{d\times r}$ is a
$d$ by $r$ matrix whose last $d-r$ rows are all null. Thus $I_{d\times
r}I_{r\times d}P_{E_{d}\to C}^{t}\mu(a)P_{C\to E_{d}}^{t}I_{d\times
r}=P_{E_{d}\to C}^{t}\mu(a)P_{C\to E_{d}}^{t}I_{d\times r}$.

Note that the construction only uses linear maps and, thus, still holds for
Z-linear invariants.

####  A.2.2 Proof of Proposition 4.12

######  Proof A.2.

Let $\mathcal{R}=(u,\mu,v)$, let $d$ be the dimension of $\mathcal{R}$ and let
$W_{1},\dots,W_{n}$ be the irreducible components of a Z-affine invariant of
$\mathcal{R}$ of length $n$ and dimension $k$. We assume, without loss of
generality, that $u\in W_{1}$.

For all $i\in\llbracket 1,n\rrbracket$, let $W_{i}=p_{i}+V_{i}$ with
$p_{i}\in\mathbb{K}^{d}$ and $V_{i}$ a vector subspace of $\mathbb{K}^{d}$ and
let $B_{i}$ be a basis of $\mathbb{K}^{d}$ obtained by completing a basis of
$V_{i}$ with arbitrary vectors.

We define $\mathcal{A}$ as $(Q,q_{0},\mathcal{X},v_{0},o,\delta)$ where:

  * •

$Q=\llbracket 1,n\rrbracket$ and $q_{0}=1$.

  * •

$\mathcal{X}=\left\\{X_{1},\dots,X_{k}\right\\}$ and
$v_{0}=(u-p_{q_{0}})P_{E_{d}\to B_{q_{0}}}I_{d\times k}$

  * •

for all $q\in Q$, $x\in\mathbb{K}^{k}$, $o(q)(x)=\left(p_{q}+xI_{k\times
d}P_{B_{q}\to E_{d}}\right)v$.

  * •

for all $q\in Q$ and $a\in\Sigma$, let $q^{\prime}\in\left\\{p\in\llbracket
1,n\rrbracket\,\middle|\,W_{q}\mu(a)\subseteq W_{p}\right\\}$ (chosen
arbitrarily). $\delta(q,a)$ will be defined by $\delta_{Q}(q,a)=q^{\prime}$
and, for all $x\in\mathbb{K}^{k}$,

$\delta_{\mathcal{X}}(q,a)(x)=\left(\left(p_{q}+xI_{k\times d}P_{B_{q}\to
E_{d}}\right)\mu(a)-p_{q^{\prime}}\right)P_{E_{d}\to B_{q^{\prime}}}I_{d\times
k}$

We can show by induction, using Claim 2, that, for all $w\in\Sigma^{*}$,

$\delta_{\mathcal{X}}(q_{0},w)\left(v_{0}\right)=\left(u\mu(w)-p_{\delta_{Q}(q_{0},w)}\right)P_{E_{d}\to
B_{\delta_{Q}(q_{0},w)}}I_{d\times k}$

Thus, for all $w\in\Sigma^{*}$,

$\llbracket\mathcal{A}\rrbracket(w)=o(\delta_{Q}(q_{0},w))\left(\delta_{\mathcal{X}}(q_{0},w)\left(v_{0}\,\right)\right)\allowbreak=\llbracket\mathcal{R}\rrbracket(w)$

The same construction can be applied to obtain the linear version of the
proposition (it is the case where $p_{i}=0$ for all $i\in\llbracket
1,n\rrbracket$).

####  A.2.3 Proof of Proposition 4.13

######  Proof A.3.

Let’s assume, without loss of generality, that
$\mathcal{A}=(Q,q_{0},\allowbreak\mathcal{X},v_{0},o,\delta)$ is an affine
$\mathrm{CRA}$ where $Q=\llbracket 1,n\rrbracket$, $q_{0}=1$,
$\mathcal{X}=\left\\{X_{1},\dots,X_{k}\right\\}$.

We define $\mathcal{R}$ as $(u,\mu,v)$, where:

  * •

$u=(v_{0},1,0,\dots,0)\in\mathbb{K}^{1\times n(k+1)}$

  * •

$v=\left(\begin{array}[]{c}o_{1}\\\ \vdots\\\
o_{n}\end{array}\right)\in\mathbb{K}^{n(k+1)\times 1}$. where, for all
$i\in\llbracket 1,n\rrbracket$, $o_{i}=\left(\begin{array}[]{c}o(i)^{(l)}\\\
o(i)^{(a)}\end{array}\right)$.

  * •

for all $a\in\Sigma$,
$\mu(a)=\left(\begin{array}[]{c|c|c}\delta_{1,1}(a)&\dots&\delta_{1,n}(a)\\\
\hline\cr\vdots&\ddots&\vdots\\\
\hline\cr\delta_{n,1}(a)&\dots&\delta_{n,n}(a)\end{array}\right)$ where, for
all $i,j\in\llbracket 1,n\rrbracket$,
$\delta_{i,j}(a)=\left(\begin{array}[]{c|c}\delta_{\mathcal{X}}(i,a)^{(l)}&0\\\\[5.0pt]
\hline\cr\delta_{\mathcal{X}}(i,a)^{(a)}&1\end{array}\right)\in\mathbb{K}^{k+1\times
k+1}$ if $\delta_{Q}(i,a)=j$ and 0 otherwise.

We can show by induction that the definition of the $\delta_{i,j}$ extends to
words and thus, for all $w\in\Sigma^{*}$,

$\displaystyle\llbracket\mathcal{R}\rrbracket(w)$ $\displaystyle=\left(v_{0}\
\delta_{\mathcal{X}}(i,w)^{(l)}+\delta_{\mathcal{X}}(i,w)^{(a)}\right)o(\delta_{Q}(q_{0},w))^{(l)}+o(\delta_{Q}(q_{0},w))^{(a)}$
$\displaystyle=o(\delta_{Q}(q_{0},w))\left(\delta_{\mathcal{X}}(q_{0},w)\left(v_{0}\,\right)\right)$
$\displaystyle\llbracket\mathcal{R}\rrbracket(w)$
$\displaystyle=\llbracket\mathcal{A}\rrbracket(w)$

Let $S=\bigcup_{i=1}^{n}\psi_{i}(\mathbb{K}^{k})$ where, for all
$i\in\llbracket 1,n\rrbracket$,
$\psi_{i}:\mathbb{K}^{k}\to\mathbb{K}^{n(k+1)}$ maps every vector
$v\in\mathbb{K}^{k}$ to the vector of $\mathbb{K}^{n(k+1)}$ that has $(v,1)$
as its $i$-th “block” of size $k+1$ and zeros everywhere else.

We show that $S$ is the desired Z-affine invariant of $\mathcal{R}$ : First,
$S$ is an invariant of $\mathcal{R}$, since $u=\psi_{1}(v_{0})\in S$ and
$\psi_{i}(x)\mu(a)=\psi_{\delta_{Q}(i,a)}(\delta_{\mathcal{X}}(i,a)(x))\in S$,
for all $\psi_{i}(x)\in S$ and $a\in\Sigma$. Then, since the $\psi_{i}$ are
affine maps, $S$ is a Z-affine set, whose irreducible components are the
$\psi_{i}(\mathbb{K}^{k})$, which have a dimension $k$ as required.

Observe that the proposition is also proved in the linear setting, since
applying this construction to a linear $\mathrm{CRA}$ yields a $\mathrm{WA}$
with the desired Z-linear invariant.

##  Appendix B Complements to Section 5

###  B.1 Proof of Lemma 5.1

######  Proof B.1.

Let $\mathcal{R}=(u,\mu,v)$ be a $\mathrm{WA}$ over alphabet $\Sigma$. Let $I$
be a Z-affine invariant of $\mathcal{R}$ of length $n$ and dimension $k$, with
irreducible components $A_{1},\ldots,A_{n}$.

We will define sets $S_{1},\ldots,S_{n}$ such that, for all
$i\in\left\\{1,\cdots,n\right\\}$, $\textup{{aff}}\left(\left\\{u\mu(w)|\ w\in
S_{i}\right\\}\right)\subseteq A_{i}$, representing a Z-affine set $J$. Given
a word $w$, we will write $u_{w}=u\mu(w)$. Since $I$ is an invariant, there is
an index $i$ such that $u_{\epsilon}=u\in A_{i}$. Thus, the set $S_{i}$ is
initialized as $\left\\{\epsilon\right\\}$ and all other sets are initially
empty.

If $J$ is not an invariant, this means there exist
$i\in\left\\{1,\ldots,n\right\\}$, $w\in S_{i}$ and $a\in\Sigma$ such that
$u_{wa}\notin J$. However, we know that since $I$ is an invariant, it must at
least contain the reachability set of $\mathcal{R}$ and thus $u_{wa}\in I$.
Hence, there exists $j$ such that $u_{wa}\in A_{j}$. Thus, we update
$S_{j}\coloneqq S_{j}\cup\left\\{w\right\\}$. Note that we still have that
$\left\\{u_{s}|\ s\in S_{j}\right\\}\subseteq A_{j}$ thus the invariant111We
heard you liked invariants, so we put invariants in your invariants.
$J\subseteq I$ is preserved.

A first observation is that each time we add a new vector to the
representation of $J$, the dimension of one of the components increases by
$1$, hence this can happen at most $(k+1)n-1$ times (assuming the dimension of
the empty set is $-1$). Similarly, each time this happens, the maximum length
of a word in the representation increases by at most $1$.

Thus, after at most $(k+1)n-1$ steps, $J$ is an invariant included in $I$, of
length $\leq n$ , with a representation of size at most $O(k^{2}n^{2})$.

###  B.2 Proof of Lemma 5.2

######  Proof B.2.

Let $\mathcal{R}=(u,\mu,v)$ be a $\mathrm{WA}$, let $c,k\in\mathbb{N}$ and let
$A_{1},\ldots,\allowbreak A_{c^{k}+1}\subseteq I_{c}(\mathcal{R})$ be spaces
satisfying the assumptions.

Assume by contradiction that $\textup{{aff}}\left(\cup_{i\in\llbracket
1,c^{k}+1\rrbracket}A_{i}\right)\not\subseteq I_{c}(\mathcal{R})$. Then, by
definition, there must exist an invariant $I$ of length $\leq c$ such that
$\textup{{aff}}\left(\cup_{i\in\llbracket
1,c^{k}+1\rrbracket}A_{i}\right)\not\subseteq I$. This means that any
component of $I$ can contain at most $c^{k-1}$ $A_{i}$s (or else it would
contain a $k$-dimensional component included in
$\textup{{aff}}\left(\cup_{i\in\llbracket 1,c^{k}+1\rrbracket}A_{i}\right)$,
which is $k$-dimensional as well). As a consequence, $I$ must have at least
$c+1$ components, which yields a contradiction.

###  B.3 Proof of Claim 1

######  Proof B.3.

Let $\mathcal{R}=(u,\mu,v)$ be a $\mathrm{WA}$, of dimension $d$, let
$c\in\mathbb{N}$. We show by induction on $k$ that if
$A_{1},\ldots,A_{c^{k}+1}\subseteq I_{c}(\mathcal{R})$ generates a subspace of
dimension $\leq k$ then there exist $1\leq i<j\leq c^{k}+1$ such that
$\textup{{aff}}\left(A_{i}\cup A_{j}\right)\subseteq I_{c}(\mathcal{R})$, and
these indices can be found in time $O(c^{p(d)})$.

For $k=0$, if two subspaces generate an affine subspace of dimension $0$, it
means that $A_{1}=A_{2}$, which are singletons. Thus
$\textup{{aff}}\left(A_{1}\cup A_{2}\right)=A_{1}\subseteq
I_{c}(\mathcal{R})$. Assume the result holds for some $k$, let us show it
holds for $k+1$. Let $A_{1},\ldots,A_{c^{k+1}+1}\subseteq I_{c}(\mathcal{R})$
be subspaces generating a space of dimension $\leq k+1$. We want to find, if
it exists, a set $P\subseteq\llbracket 1,c^{k+1}+1\rrbracket$ with
$|P|=c^{k}+1$, such that $\textup{{aff}}\left(\cup_{i\in P}A_{i}\right)$ has
dimension $\leq k$. If it exists then we use the induction assumption.
Otherwise, Lemma 5.2 yields the result. We have to show that we can find such
a set $P$, if it exists, in the given time constraint. Let
$Q\subseteq\llbracket 1,c^{k+1}+1\rrbracket$, we denote by
$A_{Q}=\textup{{aff}}\left(\cup_{i\in Q}A_{i}\right)$ the affine space
associated with $Q$. We say that $Q$ is _minimal_ if it is minimal, inclusion-
wise, among the sets associated with $A_{Q}$. Note that a minimal set has
cardinality at most $d$. Thus there are at most $(c^{d}+1)^{d+1}\leq
c^{d^{2}+2d+1}$ such sets. We say that $i\leq c^{k+1}+1$ is _compatible_ with
$Q$ if $A_{i}\subseteq A_{Q}$. Given a set $Q$ one can obtain the set of
indices compatible with $Q$ in time $c^{k+1}$. To find a set $P$ as above, one
simply has to enumerate the minimal sets for strict subsets of $A_{\llbracket
1,c^{k+1}+1\rrbracket}$, and check if one of them has a set of compatible
indices of size $\geq c^{k}+1$.

###  B.4 Proof of Theorem 5.5

The first item of the statement has already been explained in the core of the
paper.

We consider the proof of the simply exponential upper bound in the case where
the transition matrices of the given $\mathrm{WA}$ commute (and in particular,
for any $\mathrm{WA}$ on a unary alphabet). We will show it, using results and
ideas from [4] and some basic linear algebra:

######  Theorem B.4.

If $\mathcal{R}=(u,\mu,v)$ is a $d$-dimensional $\mathrm{WA}$ on a finite
alphabet $\Sigma$ such that $\left<\mu(\Sigma)\right>$ is commutative, then
the length of $\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}$ is, at
most, exponential in $d$.

Thus, in this case, both the computation of the strongest Z-linear invariant
and the resolution of the register minimization problem for linear
$\mathrm{CRA}$ can be done in ExpTime.

The proof of this theorem relies on the two following lemmas: The first
provides a constant we will use to bound the length of the strongest Z-linear
invariant and characterizes it for minimal $\mathrm{WA}$ on a unary alphabet
(see [4, Lemma 13 and Theorem 10]):

######  Lemma B.5.

For all $d\in\mathbb{N}$, there exists an integer $N\in\mathbb{N}$ such that,
for all invertible matrix $A\in\mathbb{K}^{d\times d}$,

  1. 1.

for all vector subspace $V\subseteq\mathbb{K}^{d}$, if $VA^{n}=V$ for some
$n>0$ then $VA^{N}=V$.

  2. 2.

$\overline{\left<A\right>}^{\ell}=\bigcup_{i=0}^{N-1}A^{i}\textup{{span}}\left(\left<A^{N}\right>\right)$.

Note that the value of $N$ depends only on $\mathbb{K}$ and $d$ and is
exponential in $d$.

Indeed, in the proof of [4, Theorem 10] (see also [4, Lemma 12]) $N$ is taken
to be the least common multiple of all $n\in\mathbb{N}$ such that
$\phi(n)\leq[\mathbb{K}:\mathbb{Q}]d$, where $\phi$ is Euler’s totient
function and $[\mathbb{K}:\mathbb{Q}]$ is the degree of the field extension
and a well-known property of $\phi$ is that, for all $n\geq 1$,
$\sqrt{\frac{n}{2}}\leq\phi(n)\leq n-1$. Thus
$N\leq\left(2[\mathbb{K}:\mathbb{Q}]^{2}d^{2}\right)!$

The second lemma is a direct consequence of [4, Lemma 9]:

######  Lemma B.6.

If $S\subseteq\mathbb{K}^{d\times d}$ is a monoid, then $\overline{S}^{\ell}$
has a unique irreducible component that contains the identity matrix $I_{d}$.

Last, we focus on the third statement of Theorem 5.5, showing that the
exponential bound is sharp. This is shown by the following example, where we
define a sequence of $\mathrm{WA}$ $(\mathcal{R}_{i})_{i\in\mathbb{N}}$ with a
dimension that is polynomial in $i$ and a strongest Z-linear invariant with a
length that is exponential in $i$.

######  Example B.7.

For all $i\in\mathbb{N}$, let $\mathbb{P}_{\leq i}$ denote the set of prime
numbers up to $i$, let $M_{p}=\left(\begin{array}[]{ccccc}0&1&0&\dots&0\\\
0&0&1&\dots&0\\\ \vdots&&\ddots&&\vdots\\\ 0&0&0&\dots&1\\\
1&0&0&\dots&0\end{array}\right)\in\mathbb{K}^{p\times p}$, and for all
$p\in\mathbb{P}_{\leq i}$ (it is the permutation matrix associated with the
$p$-cycle $(1\,2\,\dots\,p)$).

Let $d=\sum_{p\in\mathbb{P}_{\leq i}}p$ and
$\mathcal{R}_{i}=(u_{i},\mu_{i},v_{i})$ be a $d$-dimensional $\mathrm{WA}$, on
the unary alphabet $\Sigma=\left\\{a\right\\}$, where
$u_{i}=v_{i}^{t}=(1\,2\,\dots\,d)$ and
$\mu_{i}(a)=\left(\begin{array}[]{c|c|c|c}M_{2}&0&\dots&0\\\ \hline\cr
0&M_{3}&\dots&0\\\ \hline\cr\vdots&&\ddots&\vdots\\\ \hline\cr
0&\dots&0&M_{\max(\mathbb{P}_{\leq i})}\end{array}\right)$ is a
$d$-dimensional block diagonal matrix.

Observe that the monoid generated by $\mu_{i}(a)$ is a cyclic group of order
$n=\textup{{lcm}}(\mathbb{P}_{\leq i})=\prod_{p\in\mathbb{P}_{\leq i}}p$.
Thus, the strongest Z-linear invariant of $\mathcal{R}_{i}$ has a length of
$n$, since it is the union of $n$ lines.

###  B.5 Proof of Theorem B.4

First, observe that, for all matrices $M\in\mathbb{K}^{d\times d}$,
$(\textup{{ker}}\left(M^{i}\right))_{i\in\mathbb{N}}$ is an increasing
sequence of vector subspaces of $\mathbb{K}^{d}$. Thus, for all
$i\in\mathbb{N}$,
$\textup{{ker}}\left(M^{d}\right)=\textup{{ker}}\left(M^{d+i}\right)$ and
$\mathbb{K}^{d}=\textup{{im}}\left(M^{d}\right)\oplus\textup{{ker}}\left(M^{d}\right)$.

Let $r$ be the rank of $M^{d}$ and $B$ be a basis of $\mathbb{K}^{d}$ whose
first $r$ (resp. last $d-r$) vectors form a basis of
$\textup{{im}}\left(M^{d}\right)$ (resp. $\textup{{ker}}\left(M^{d}\right)$).
Then, $P_{B\to E_{d}}M^{d}P_{E_{d}\to B}$ is a matrix of the form
$\left(\begin{array}[]{c|c}M^{\prime}&0\\\ \hline\cr 0&0\end{array}\right)$
with $M^{\prime}\in\mathbb{K}^{r\times r}$ an invertible matrix.

We can then bound the length of
$\overline{\left<M\right>}^{\ell}=\bigcup_{i=0}^{d-1}M^{i}\overline{\left<M^{d}\right>}^{\ell}$
using the bound for a single invertible matrix of Lemma B.5 by observing that
$\left<M^{d}\right>=P_{E_{d}\to B}\left<P_{B\to E_{d}}M^{d}P_{E_{d}\to
B}\right>P_{B\to E_{d}}$, and $\left<M^{\prime}\right>$ is isomorphic (as a
semigroup) to $\left<P_{B\to E_{d}}M^{d}P_{E_{d}\to B}\right>$ by an
isomorphism which is also a linear map. Thus,
$\textup{{length}}(\overline{\left<M^{d}\right>}^{\ell})\leq\textup{{length}}(\overline{\left<M^{\prime}\right>}^{\ell})$
which is exponential in $r\leq d$.

This approach can be generalized to an arbitrary number of matrices
$M_{1},\dots,M_{n}$, provided that $\left<M_{1},\dots,M_{n}\right>$ is
commutative, as we show next.

If $M_{1},\dots,M_{n}$ are invertible
$\overline{\left<M_{1},\dots,M_{n}\right>}^{\ell}$ has a unique irreducible
component $W$ containing the identity matrix (thanks to Lemma B.6) and, for
all $i\in\llbracket 1,n\rrbracket$, $M_{i}$ acts by permutation on a finite
number of irreducible components of
$\overline{\left<M_{1},\dots,M_{n}\right>}^{\ell}$, thus there exists
$N_{i}>0$ such that $WM_{i}^{N_{i}}=W$. We can take $N_{1}=\dots=N_{n}=N$
given by Lemma B.5 (which is exponential in $d$). Thus, the length of
$\overline{\left<M_{1},\dots,M_{n}\right>}^{\ell}=\bigcup_{j_{i}\in\llbracket
0,N-1\rrbracket}M_{1}^{j_{1}}M_{2}^{j_{2}}\cdots M_{n}^{j_{r}}W$ is at most
$N^{n}$. Like previously, we can use this result to bound the length in the
general case.

For all $I\subseteq\llbracket 1,n\rrbracket$, let
$M_{I}=\left\\{M_{i}\,\middle|\,i\in I\right\\}$ and let, for all
$k\in\mathbb{N}$,

$\left<M_{I}\right>^{\leq k}=\left\\{\prod_{i\in
I}M_{i}^{j_{i}}\,\middle|\,\forall i\in I,j_{i}\in\llbracket
0,k\rrbracket\right\\}$

then

$\left<M_{1},\dots,M_{n}\right>=\left(\left(\prod_{i=1}^{n}M_{i}\right)^{d}\left<M_{1},\dots,M_{n}\right>\right)\bigcup\left(\bigcup_{k=1}^{n-1}\left(\bigcup_{\begin{subarray}{c}I\subseteq\llbracket
1,n\rrbracket\\\ |I|=k\end{subarray}}\left<M_{I}\right>^{\leq
d-1}\left<M_{\llbracket 1,n\rrbracket\setminus I}\right>\right)\right)$

Thus, it suffices to show that
$\overline{\left(\prod_{i=1}^{n}M_{i}\right)^{d}\left<M_{1},\dots,M_{n}\right>}^{\ell}$
is of length at most exponential in $d$.

Let $r$ be the rank of $\left(\prod_{i=1}^{n}M_{i}\right)^{d}$ and let $B$ be
a basis of $\mathbb{K}^{d}$ whose first $r$ (resp. last $d-r$) vectors form a
basis of $\textup{{im}}\left(\left(\prod_{i=1}^{n}M_{i}\right)^{d}\right)$
(resp. $\textup{{ker}}\left(\left(\prod_{i=1}^{n}M_{i}\right)^{d}\right)$).

Then, $P_{B\to E_{d}}\left(\prod_{i=1}^{n}M_{i}\right)^{d}P_{E_{d}\to
B}=\left(\begin{array}[]{c|c}M^{\prime}&0\\\ \hline\cr 0&0\end{array}\right)$
for some invertible matrix $M^{\prime}\in\mathbb{K}^{r\times r}$.

For all $i\in\llbracket 1,n\rrbracket$,
$\textup{{im}}\left(\left(\prod_{j=0}^{n}M_{j}\right)^{d}\right)=\textup{{im}}\left(\left(\prod_{j=0}^{n}M_{j}\right)^{d}M_{i}\right)$.
Thus, $P_{B\to E_{d}}M_{i}P_{E_{d}\to B}$ has the form
$\left(\begin{array}[]{c|c}M^{\prime}_{i}&0\\\ \hline\cr
M^{\prime\prime}_{i}&M^{\prime\prime\prime}_{i}\end{array}\right)$ with
$M^{\prime}_{i}\in\mathbb{K}^{r\times r}$ invertible because $M^{\prime}$ is
invertible and $\min_{i\in\llbracket
1,n\rrbracket}\textsf{rank}(M_{i}^{\prime})\geq\textsf{rank}\left(\left(\prod_{i=1}^{n}M_{i}^{\prime}\right)^{d}\right)=\textsf{rank}(M^{\prime})=r$.

Since

$\overline{\left(\prod_{i=1}^{n}M_{i}\right)^{d}\left<M_{1},\dots,M_{n}\right>}^{\ell}=P_{E_{d}\to
B}\overline{P_{B\to
E_{d}}\left(\prod_{i=1}^{n}M_{i}\right)^{d}\left<M_{1},\dots,M_{n}\right>P_{E_{d}\to
B}}^{\ell}P_{B\to E_{d}}$

we conclude by noting that
$M^{\prime}\left<M_{1}^{\prime},\dots,M_{n}^{\prime}\right>$ is isomorphic (as
a semigroup) to
$P_{B\to
E_{d}}\left(\prod_{i=1}^{n}M_{i}\right)^{d}\left<M_{1},\dots,M_{n}\right>P_{E_{d}\to
B}$ by an isomorphism which is a linear map.

###  B.6 Proof of Theorem 5.10

The inequalities stated in Theorem 5.10 are graphically depicted on Figure 5.

nb of statesnb of
registers$1$$n^{\prime}\leq\textsf{length}(\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell})$$d^{\prime}\leq
d$$\textsf{dim}(\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell})$

Figure 5: Tradeoff between number of states and registers: drawing the shape
of the set of optimal pairs.

Regarding the proof of the theorem, we know, thanks to Proposition 2.8, that
if one wants to minimize the number of states of the $\mathrm{CRA}$, then it
is possible to build a $\mathrm{CRA}$ with a single state, and the minimal
number of registers is the dimension $d^{\prime}$ of any minimal $\mathrm{WA}$
realizing $f$ (hence $d^{\prime}\leq d$).

On the other side, if one wants to minimize the number of registers, then
Theorem 4.7 ensures that the minimal number of registers is exactly
$\textsf{dim}(\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell})$, and
for this value, the minimal number of states is upper bounded by
$\textsf{length}(\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell})$.

(This is valid in the affine setting as well thanks to Theorem 4.15)

###  B.7 Details of Remark 5.11

To illustrate Remark 5.11, we give an example of rational series which
illustrates the expected situation.

######  Example B.8.

Let $n\in\mathbb{N}$. An $n$-dimensional permutation matrix is an $n$ by $n$
matrix that has exactly one 1 in each row and each column and zeros everywhere
else. The set $\textup{{Perm}}_{n}$ of permutation matrices together with
matrix multiplication form a group of order $n!$ that is isomorphic to the
symmetric group which can be generated using two elements.
$\overline{\textup{{Perm}}_{n}}^{\ell}$ is one-dimensional and has $n!$
irreducible components, as it is a union of $n!$ lines.

It is then possible, using a four-letter alphabet and these permutation
matrices, to define a $2n$-dimensional $\mathrm{WA}$ with a strongest Z-linear
invariant that is decomposed into the union of $n!$ one-dimensional
irreducible components and a $(n-1)$-dimensional one, such that all the one-
dimensional components can be merged together without raising the dimension of
the invariant. We proceed as follows:

Take two generators of $\textup{{Perm}}_{n}$, e.g. let $C_{n}$ and $T_{n}$ be
the matrices of $\textup{{Perm}}_{n}$ corresponding to the cycle
$(1\,2\,\dots\,\allowbreak n)$ and the transposition $(1\,2)$ respectively and
let $\mathcal{R}=(u,\mu,v)$ be the $2n$-dimensional $\mathrm{WA}$, on
$\Sigma=\left\\{a,b,c,d\right\\}$, defined by:
$u=(1\,2\,\dots\,n\,|\,0\,\dots\,0\,1)\in\mathbb{K}^{1\times 2n}$,
$\mu(a)=\left(\begin{array}[]{c|c}C_{n}&0\\\ \hline\cr
0&I_{n}\end{array}\right)$, $\mu(b)=\left(\begin{array}[]{c|c}T_{n}&0\\\
\hline\cr 0&I_{n}\end{array}\right)$, $\mu(c)=\left(\begin{array}[]{c|c}0&0\\\
\hline\cr 0&M\end{array}\right)$ and $\mu(d)=\left(\begin{array}[]{c|c}0&0\\\
\hline\cr 0&M^{\prime}\end{array}\right)$ where
$M=\left(\begin{array}[]{c|c}I_{n-1}&0\\\ \hline\cr e_{1}&1\end{array}\right)$
and $M^{\prime}=\left(\begin{array}[]{c|c}C_{n-1}&0\\\ \hline\cr
0&1\end{array}\right)$. $v\in\mathbb{K}^{n\times 1}$ can be arbitrary.

Note that $\left<\mu(a),\mu(b)\right>=\left\\{\left(\begin{array}[]{c|c}P&0\\\
\hline\cr
0&I_{n}\end{array}\right)\,\middle|\,P\in\textup{{Perm}}_{n}\right\\}$ and,
for all $x\in\mathbb{K}^{1\times n}$ and
$y=(y_{1},y_{2},\dots,y_{n-1},1)\in\mathbb{K}^{1\times n}$

$\displaystyle(x\,|\,y)\mu(c)=(0\,|\,(y_{1}+1),y_{2},\dots,y_{n-1},1)$
$\displaystyle(x\,|\,y)\mu(d)=(0\,|\,y_{n-1},y_{1},\dots,y_{n-2},1)$

Then, $\textup{{LR}}\left(\mathcal{R}\right)=S_{1}\cup S_{2}$ where

$\displaystyle
S_{1}=\left\\{\Bigl{(}(1\,2\,\dots\,n)P\,|\,0\,\dots\,0\,1\Bigr{)}\,\middle|\,P\in\textup{{Perm}}_{n}\right\\}$
$\displaystyle
S_{2}=\left\\{\Bigl{(}0\,\dots\,0\,|\,l_{1}\,\dots\,l_{n-1}\,1\Bigr{)}\,\middle|\,(l_{1}\,\dots\,l_{n-1})\in\mathbb{N}^{n-1}\right\\}$

Thus, $\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}$ is the union
of $\textup{{span}}\left(S_{2}\right)$ and the $n!$ lines, going through the
origin, directed by the vectors of $S_{1}$.

Since $\dim\left(\textup{{span}}\left(\textup{{Perm}}_{n}\right)\right)=n-1$
i.e.
$\dim\left(\textup{{span}}\left(S_{1}\right)\right)=n-1=\dim\left(\textup{{span}}\left(S_{2}\right)\right)$,
we can merge together the one-dimensional irreducible components into a single
one (which is $\textup{{span}}\left(S_{1}\right)$). We get this way a Z-linear
invariant
$I=\textup{{span}}\left(S_{1}\right)\cup\textup{{span}}\left(S_{2}\right)$
(which is an invariant because for all $a\in\Sigma$ and
$i\in\left\\{1,2\right\\}$, there exists $j\in\left\\{1,2\right\\}$ such that
$S_{i}\mu(a)\subseteq S_{j}$) with the same dimension as
$\overline{\textup{{LR}}\left(\mathcal{R}\right)}^{\ell}$ but a length of 2,
thus reducing the number of states of the corresponding $\mathrm{CRA}$ to 2
while keeping the same number of registers.