# On Tree Automata, Generating Functions, and Differential Equations

Rida Ait El Manssour
CNRS, IRIF, France  Vincent Cheval
University of Oxford, UK  Mahsa Shirmohammadi
CNRS, IRIF, France  James Worrell
University of Oxford, UK

###### Abstract

In this paper we introduce holonomic tree automata: a common extension of
weighted tree automata and holonomic recurrences. We show that the generating
function of the tree series represented by such an automaton is differentially
algebraic. Conversely, we give an algorithm that inputs a differentially
algebraic power series, represented as a solution of a rational dynamical
system, and outputs an automaton whose generating function is the given
series. Such an automaton yields a recurrence that can be used to compute the
terms of the power series. We use the algorithm to obtain automaton
representations of exponential generating functions of families of
combinatorial objects given as combinatorial species. Using techniques from
differential algebra, we show that it is decidable both whether two automata
represent the same formal tree series and whether they have the same
generating function.

##  1 Introduction

###  1.1 Overview

Weighted automata are a means of representing and effectively manipulating
formal power series. Weighted word automata determine power series on non-
commuting variables [BR10, Chapter 1], while weighted tree automata represent
formal tree series: see [DKV09, DPV05]. (A formal tree series is a mapping
that assigns numbers to trees, e.g., the function sending an arithmetic
expression to its value is realisable by a weighted tree automaton [BR82,
Example 6.2].) Each such automaton also has a _census generating function_ ,
which is a univariate power series whose $n$-th coefficient denotes the total
weight of all words or trees, respectively, of size $n$.

The generating function of a weighted word automaton is a rational power
series while the generating function of a weighted tree automaton in an
algebraic power series. The correspondence between weighted automata and their
generating functions extends to the class of differentially finite power
series (power series $f(x)$ that satisfy linear differential equations
$P_{0}(x)f(x)+P_{1}(x)f^{\prime}(x)+\cdots+P_{k}(x)f^{(k)}(x)=0$ with
polynomial coefficients) which subsumes the class of algebraic power series.
It is well-known that a power series $f(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$ is
differentially finite if and only if the sequence $(a_{n})_{n=0}^{\infty}$ of
coefficients is _holonomic (also called $P$-recursive)_, i.e., the sequence
satisfies a linear recurrence with polynomial coefficients [Kau23]. An
automata formulation of such sequences is given in [Reu12].

In this paper we introduce a common generalisation of weighted tree automata
and holonomic recurrences, called holonomic tree automata, that compute formal
tree series. In a holonomic tree automaton the weight of each transition is a
rational function in the size of the trees involved in the transition. Our
main results concern decidability and expressiveness of the new model and
focus on the link between automata and their generating functions. The
corresponding class of generating functions goes beyond differentially finite
series to include a general class of differentially algebraic power series.

Recall that a formal power series $f\in\mathbb{Q}[\\![x]\\!]$ is
_differentially algebraic_ if it satisfies a differential equation
$P(f,f^{\prime},\ldots,f^{(k)})=0$ for some polynomial $P(y_{0},\ldots,y_{k})$
with coefficients in $\mathbb{Q}[x]$. Every such series can be expressed as (a
component) of a solution of a system of first-order differential equations
$y^{\prime}_{1}=P_{1}(y_{1},\ldots,y_{k}),\ldots,y_{k}^{\prime}=P_{k}(y_{1},\ldots,y_{k})$
for rational functions $P_{1},\ldots,P_{k}\in\mathbb{Q}(x_{1},\ldots,x_{k})$.
The latter is called a _rational dynamical system_ [OPV22].111Whether there
exists a single rational dynamical system that has the same set of solutions
as the equation $P(f,f^{\prime},\ldots,f^{(k)})=0$ is called the _rational
realisation_ problem [FOR92, NS09] and is equivalent to the variety defined by
$P$ admitting a rational parameterisation. Our main results are as follows:

  * •

We show that the class of generating functions of holonomic tree automata is
closed under sum, Cauchy product, inverse, derivative, integration, forward
and backward shift (Theorem 7 in Appendix A). We moreover show that every such
series is differentially algebraic (Theorem 2).

  * •

Conversely, we give an algorithm that inputs a differentially algebraic power
series $f$, expressed as a (component of a) solution of a rational dynamical
system

$\displaystyle y^{\prime}_{1}=Q_{1}(y_{1},\ldots,y_{k})\quad\ldots\quad
y^{\prime}_{k}=Q_{k}(y_{1},\ldots,y_{k})\,,$ (1)

in which the rational functions $Q_{1},\ldots,Q_{k}$ are defined at
$(y_{1}(0),\ldots,y_{k}(0))$, and outputs an automaton whose generating
function equals $f$ (Theorem 6). To illustrate the utility of this procedure,
we give in Section 4.1 a collection of rational dynamical systems that
characterise the exponential generation functions arising from standard
constructions of combinatorial species [BLL98]. This allows us to go from a
specification of a combinatorial species to an automaton that represents its
exponential generating function.

  * •

We give a procedure to determine whether two automata represent the same
formal tree series (Corollary 1). More specifically we give an effective bound
on the size of the smallest tree on which two non-equivalent automata differ.
This result is obtained as a corollary of a procedure for determining whether
the generating function of a given holonomic tree automaton is identically
zero (Theorem 5). The latter relies on techniques from differential
algebra—specifically an effective version of the differential Nullstellensatz.

###  1.2 Weighted and Holonomic Tree Automata

Let $\Sigma$ be a ranked alphabet, that is, $\Sigma$ is a finite set of
function symbols each having a non-negative integer arity. For
$k\in\mathbb{N}$ we write $\Sigma_{k}$ for the set of symbols in $\Sigma$ of
arity $k$. Let $T_{\Sigma}$ be the set of terms over this alphabet, i.e.,
$T_{\Sigma}$ is the smallest set that contains all symbols of arity $0$ and
such that if $\sigma$ has arity $k$ and $t_{1},\ldots,t_{k}\in T_{\Sigma}$
then $\sigma(t_{1},\ldots,t_{k})\in T_{\Sigma}$. We consider elements of
$T_{\Sigma}$ as ordered trees where the vertices of $t\in T_{\Sigma}$ are its
sub-terms and, for a $k$-ary symbol $\sigma\in\Sigma$, the tree
$\sigma(t_{1},\ldots,t_{k})$ has list of children $t_{1},\ldots,t_{k}$. The
_size_ $\|t\|$ of a term $t\in T_{\Sigma}$ is the number of internal nodes and
is defined inductively by $\|\sigma\|:=0$ for $\sigma$ a nullary symbol and
$\|\sigma(t_{1},\ldots,t_{k})\|:=1+\|t_{1}\|+\cdots+\|t_{k}\|$ for $\sigma$
having arity $k\geq 1$.

#### Weighted Tree Automata

As a prelude to the central definition of the paper we introduce the notion of
weighted tree automaton (also called a multilinear representation) [BR82]. To
this end, recall that the Kronecker product of two row vectors is defined by

$\begin{pmatrix}u_{1}&u_{2}&\cdots&u_{m}\end{pmatrix}\otimes\begin{pmatrix}v_{1}&v_{2}&\cdots&v_{n}\end{pmatrix}:=\begin{pmatrix}u_{1}v_{1}&u_{1}v_{2}&\cdots&u_{m}v_{n-1}&u_{m}v_{n}\end{pmatrix}\,.$

The operation is associative and the nullary Kronecker product is the $1\times
1$ identity matrix.

A _weighted tree automaton_ over alphabet $\Sigma$ is a pair
$\mathcal{A}=(d,\mu)$, where $d\in\mathbb{N}$ is the dimension and $\mu$ is a
function with domain $\Sigma$ such that $\mu(\sigma)\in\mathbb{Q}^{d^{k}\times
d}$ is a matrix of rational numbers for $\sigma\in\Sigma_{k}$. The map $\mu$
induces a function $\widetilde{\mu}:T_{\Sigma}\rightarrow\mathbb{Q}^{1\times
d}$ that is defined inductively by specifying that

$\displaystyle\widetilde{\mu}(\sigma(t_{1},\ldots,t_{k})):=(\widetilde{\mu}(t_{1})\otimes\cdots\otimes\widetilde{\mu}(t_{k}))\cdot\mu(\sigma)$

for a $k$-ary symbol $\sigma$. In other words, $\widetilde{\mu}(t)$ is given
by an iterated matrix product determined by parsing the tree $t$ from the
leaves to the root. The formal tree series defined by $\mathcal{A}$ is the map
$\mathcal{A}[\\![\cdot]\\!]:T_{\Sigma}\rightarrow\mathbb{Q}$ by
$\mathcal{A}[\\![t]\\!]:=\widetilde{\mu}(t)_{1}$.

Two weighted tree automata over the same alphabet are said to be _equivalent_
if they induce the same tree series. Equivalence of weighted tree automata was
shown to be decidable in randomised polynomial time in [Sei90] and later to be
logspace interreducible with Polynomial Identity Testing in [MW15].

We also associate with $\mathcal{A}$ its _generating function_

$\displaystyle
f_{\mathcal{A}}(x)=\sum_{n=0}^{\infty}\left(\sum_{t:\|t\|=n}\mathcal{A}[\\![t]\\!]\right)x^{n}\,,$
(2)

in which the coefficient of $x^{n}$ is the total value of all trees of size
$n$. The generating function of a weighted tree automaton is an algebraic
power series [BR82, Proposition 7.2]. Note that two automata that represent
different tree series can have the same generating function, since the latter
groups together all trees of the same size. Equivalence of generating
functions of weighted tree automata lies in the counting hierarchy [BCN+23].

#### Holonomic Tree Automata

Let $\mathbb{Q}_{u}(x_{0},\ldots,x_{k})$ be the subring of
$\mathbb{Q}(x_{0},\ldots,x_{k})$ consisting of rational functions of the form

$\frac{P(x_{0},\ldots,x_{k})}{Q_{0}(x_{0})\cdots Q_{k}(x_{k})}$

where $P\in\mathbb{Q}[x_{0},\ldots,x_{k}]$ is a multivariate polynomial and
$Q_{i}\in\mathbb{Q}[x_{i}]$ for $i\in\\{0,\ldots,k\\}$ are univariate
polynomials such that $Q_{0}$ has no positive integer root and
$Q_{1},\ldots,Q_{k}$ have no nonnegative integer root. Since the set of
allowed denominators is closed under products
$\mathbb{Q}_{u}(x_{0},\ldots,x_{k})$ is indeed a ring. The restriction of the
codomain of $\mu$ to matrices with entries in the subring $\mathbb{Q}_{u}$
will be used in the proof that the generating function of a holonomic tree
automaton is differentially algebraic.

The notion of holonomic tree automata generalises that of weighted tree
automata. A _holonomic tree automaton_ over alphabet $\Sigma$ is a pair
$\mathcal{A}=(d,\mu)$, where $d\in\mathbb{N}$ is the dimension and $\mu$ is a
map with domain $\Sigma$ such that $\mu(\sigma)\in\mathbb{Q}^{1\times d}$ for
$\sigma\in\Sigma_{0}$ and, for $k\geq 1$ and $\sigma\in\Sigma_{k}$,
$\mu(\sigma)\in\mathbb{Q}_{u}(x_{0},\ldots,x_{k})^{d^{k}\times d}$ is a matrix
of rational functions.

The map $\mu$ induces a function
$\widetilde{\mu}:T_{\Sigma}\rightarrow\mathbb{Q}^{1\times d}$, inductively
defined by specifying that $\widetilde{\mu}(\sigma)=\mu(\sigma)$ for
$\sigma\in\Sigma_{0}$ and for $k\geq 1$ and $\sigma\in\Sigma_{k}$ and
$t_{0}=\sigma(t_{1},\ldots,t_{k})$,

$\displaystyle\widetilde{\mu}(t_{0}):=(\widetilde{\mu}(t_{1})\otimes\cdots\otimes\widetilde{\mu}(t_{k}))\cdot\mu(\sigma)(\|t_{0}\|,\ldots,\|t_{k}\|)\,.$

We define the formal tree series represented by $\mathcal{A}$ to be
$\mathcal{A}[\\![\cdot]\\!]:T_{\Sigma}\rightarrow\mathbb{Q}$ by
$\mathcal{A}[\\![t]\\!]:=\widetilde{\mu}(t)_{1}$.

The definition of the _generating function_ $f_{\mathcal{A}}$ of a holonomic
tree automaton $\mathcal{A}$ is exactly as for a weighted tree automaton,
namely via Equation (2). In general $f_{\mathcal{A}}$ need not be algebraic,
unlike for weighted tree automata, but we will show that it is differentially
algebraic.

#### Examples.

In Theorem 6 we give a procedure that inputs a power series, represented as a
rational dynamical system and outputs a holonomic automata whose generating
function equals the given power series. Here, we give some specific examples
of holonomic automata that arise from differential equations that have a
combinatorial flavour. In all the following examples the signature is
$\Sigma=\\{\sigma_{0},\sigma_{1},\sigma_{2}\\}$ where $\sigma_{k}$ has arity
$k$.

######  Example 1 (Bell numbers).

Recall that the sequence $(b_{n})_{n=0}^{\infty}=(1,1,2,5,15,52,203,\ldots)$
of Bell numbers has general term the number of partitions of the set
$\\{1,\ldots,n\\}$. As noted in [BR90], the exponential generating function
$f_{B}(x):=\sum_{n=0}^{\infty}\frac{b_{n}}{n!}x^{n}$ is (the $f$-component of)
a solution of the system of differential equations $f^{\prime}(x)=f(x)g(x)$
and $g^{\prime}(x)=g(x)$.

We specify an automaton $\mathcal{A}=(2,\mu)$ over alphabet $\Sigma$ such that
$f_{\mathcal{A}}=f_{B}$. The weight function is defined as follows:

$\mu(\sigma_{0}):=\begin{bmatrix}1&1\\\
\end{bmatrix}\qquad\mu(\sigma_{1}):=\begin{bmatrix}0&0\\\ 0&\frac{1}{x_{0}}\\\
\end{bmatrix}\qquad\mu(\sigma_{2}):=\begin{bmatrix}\boldsymbol{0}_{2\times
1}&\boldsymbol{0}_{2\times 1}\\\ \frac{1}{x_{0}}&0\\\ 0&0\end{bmatrix}$

We outline a combinatorial interpretation of the equality
$f_{\mathcal{A}}=f_{B}$. The set $\\{t\in
T_{\Sigma}:[\\![\mathcal{A}]\\!](t)\neq 0\\}$ comprises those trees $t\in
T_{\Sigma}$ such that all internal nodes in $t$ reachable from the root by
zero or more steps of the left-child relation have arity two, while all other
internal nodes have arity one (see Figure 1). For such a tree $t$ of size $n$,
deleting all edges between a node and its left-child one obtains a forest of
chains. If the chains have respective sizes $k_{1},\ldots,k_{s}$, reading from
left to right in $t$, we have

$\displaystyle[\\![\mathcal{A}]\\!](t)=\frac{1}{k_{1}!\cdots
k_{s}!}\,\frac{k_{1}}{k_{1}+k_{2}}\cdots\frac{k_{s-1}}{k_{1}+\cdots+k_{s}}\,.$
(3)

Note that every labelling of the internal nodes of $t$ in the numbers
$\\{1,\ldots,n\\}$ naturally yields a partition of $\\{1,\ldots,n\\}$. For any
fixed partition $\pi$ of $\\{1,\ldots,n\\}$, summing the expression for
$[\\![\mathcal{A}]\\!](t)$ in (3) over all trees $t\in T_{\Sigma}$ and
labellings of the nodes of $t$ that yield $\pi$, we obtain $n!$.

######  Example 2 (Labelled trees).

Let $(t_{n})_{n=0}^{\infty}=(0,1,2,9,64,625,\ldots)$ be the sequence whose
general term counts the number of labelled rooted trees with $n$ nodes. It is
classical that $t_{n}=n^{n-1}$ for all $n\geq 1$. From this closed form (or
from the characterisation of labelled trees as a combinatorial species) it can
be seen that the exponential generating function
$f_{T}(x)=\sum_{n=0}^{\infty}\frac{t_{n}}{n!}x^{n}$ is the $f$-component of
the solution of the system

$f(x)=xg(x),\quad g^{\prime}(x)=f^{\prime}(x)g(x)\,.$

From the above system of equations we obtain an automaton
$\mathcal{A}=(2,\mu)$ over alphabet $\Sigma$ whose generating function
coincides with $f_{T}$. The definition of $\mu$ is as follows:

$\mu(\sigma_{0})=\begin{bmatrix}0&1\\\
\end{bmatrix}\qquad\mu(\sigma_{1})=\begin{bmatrix}0&0\\\ 1&0\\\
\end{bmatrix}\qquad\mu(\sigma_{2})=\begin{bmatrix}\boldsymbol{0}_{3\times
1}&\boldsymbol{0}_{3\times 1}\\\ 0&\frac{x_{2}+1}{x_{0}}\\\ \end{bmatrix}$

The equality $f_{\mathcal{A}}=f_{T}$ again admits a combinatorial
interpretation. The set $\\{t\in T_{\Sigma}:[\\![\mathcal{A}]\\!](t)\neq 0\\}$
comprises those trees $t\in T_{\Sigma}$ in which the root has arity one and
all other internal nodes have arity two. Each such tree $t$ determines in a
natural way a rooted unordered tree $\tau$ (in which there is no bound on the
number of children of a node): the idea is that a left-child in $t$ encodes
the sibling relation in $\tau$ (see Figure 2). Now every labelling of $t$
yields a labelling of $\tau$ and, similarly to the previous example, summing
$[\\![\mathcal{A}]\\!](t)$ over all trees $t$ and labellings of the nodes of
$t$ that give the same labelled rooted unordered tree gives $n!$.

$a$$b$$c$$d$$e$$f$$g$$h$$d$$b$$a$$f$$e$$c$$g$$h$ Figure 1: Encoding partitions
as ranked binary trees. $a$$b$$c$$d$$e$$f$$g$$h$$i$$a$$d$$c$$b$$f$$e$$g$$h$$i$
Figure 2: Encoding rooted non-plane trees as ranked binary trees.

######  Example 3.

Consider the solution $y_{1}(x)$ of the differential equation
$(y_{1}^{\prime})^{3}+y_{1}^{3}=1$ such that $y_{1}(0)=0$ and
$y^{\prime}_{1}(0)=1$. Differentiating the equation we deduce that $y_{1}(x)$
also satisfies
$3(y^{\prime}_{1})^{2}y^{\prime\prime}_{1}+3(y_{1})^{2}y^{\prime}_{1}=0$,
which leads to the following rational dynamical system:

$\left\\{\begin{array}[]{l}y^{\prime}_{1}=y_{2}\\\
y^{\prime}_{2}=-\frac{y^{2}_{1}}{y_{2}}\end{array}\right.$

As $y_{2}(0)=y^{\prime}_{1}(0)\neq 0$, the proof of Theorem 6 constructs an
automaton ${\mathcal{A}}=(4,\mu)$ such that $f_{\mathcal{A}}(x)=y_{1}(x)$ (see
Example 5 for more details). The weight function is defined by

$\mu(\sigma_{0})=\begin{bmatrix}0&1&0&0\end{bmatrix}\qquad\mu(\sigma_{1})(x_{0},x_{1})=\begin{bmatrix}0&0&0&0\\\
1&0&0&0\\\ 0&\frac{1}{x_{0}+1}&0&0\\\ 0&0&\frac{1}{x_{0}+1}&0\end{bmatrix}$

and

$\mu(\sigma_{2})(x_{0},x_{1},x_{2})=\begin{bmatrix}\boldsymbol{0}_{6\times
1}&\boldsymbol{0}_{6\times 1}&\boldsymbol{0}_{6\times
1}&\boldsymbol{0}_{6\times 1}\\\ 0&0&0&-1\\\ \boldsymbol{0}_{3\times
1}&\boldsymbol{0}_{3\times 1}&\boldsymbol{0}_{3\times
1}&\boldsymbol{0}_{3\times 1}\\\ 0&0&-\frac{x_{2}+1}{x_{0}+1}&0\\\
\boldsymbol{0}_{5\times 1}&\boldsymbol{0}_{5\times 1}&\boldsymbol{0}_{5\times
1}&\boldsymbol{0}_{5\times 1}\end{bmatrix}$

Running the automaton, we compute its generating function $f_{\mathcal{A}}$
as:

$y_{1}(x)=x-\frac{2}{4!}x^{4}-\frac{20}{7!}x^{7}-\frac{3320}{10!}x^{10}-\frac{1598960}{13!}x^{13}-\frac{1757280800}{16!}x^{16}-\ldots$

###  1.3 Organisation of the Paper

Our main contributions concern the expressiveness and effectiveness of
holonomic tree automata, both in terms of their generating functions and the
formal tree series that they define.

In Section 2 we show that the generating function $f_{\mathcal{A}}$ of a
holonomic tree automaton $\mathcal{A}$ is (effectively) differentially
algebraic. To show this we extract from the definition of $\mathcal{A}$ a
system of differential polynomials that have a unique common zero in power
series, a component of which is $f_{\mathcal{A}}$. Now a differential-
algebraic version of Artin’s approximation theorem [DL84, Theorem 2.1] states
that any power-series zero of a finite collection of differential polynomials
can be approximated to arbitrary order by a zero that is a differentially
algebraic power-series. We conclude that $f_{\mathcal{A}}$, being (a component
of) a _unique_ solution of such a system, is itself differentially algebraic.

In Section 3 we give a procedure for determining whether the generating
function $f_{\mathcal{A}}$ of a holonomic automaton $\mathcal{A}$ is
identically zero. Here we again exploit the fact that $f_{\mathcal{A}}$ is a
component of the unique zero in power series of a system of differential
polynomials. This allows us to reduce the problem of determining zeroness of
$f_{\mathcal{A}}$ to that of checking whether a certain collection of
differential polynomials has a common zero in power series. Here we use an
effective version of the differential Nullstellensatz [OPV22]. This gives an
explicit bound $B$ such that our collection of differential polynomials has no
zero in power series if and only if the polynomial ideal generated by the
first $B$ derivatives has no common zero. From this we deduce that
$f_{\mathcal{A}}$ is identically zero if and only if it is zero modulo
$x^{B+1}$ and decidability follows immediately.

As a corollary of the ability to check zeroness of the generating function
$f_{\mathcal{A}}$ we can decide whether the generating functions of two given
holonomic tree automata $\mathcal{A}$ and $\mathcal{B}$ are equal and also
whether their formal tree series are equal, that is, whether
$[\\![\mathcal{A}]\\!](t)=[\\![\mathcal{B}]\\!](t)$ for all trees $t$. In the
latter case we obtain an explicit upper bound $B$ such that if
$[\\![\mathcal{A}]\\!]\neq[\\![\mathcal{B}]\\!]$ then the two functions differ
already on a tree of size $B$.

In Section 4 we give an effective procedure that inputs a power series $f$,
presented as the solution of a rational dynamical system (subject to a
condition on the poles of the rational function, as specified above), and
outputs a holonomic tree automaton $\mathcal{A}$ whose generating function
equals $f$. We illustrate this procedure with several examples. Furthermore,
in Section 4.1 we give a translation of a standard collection of
specifications on combinatorial species to rational dynamical systems that
define their exponential generating functions. Combining this translation with
the above-mentioned procedure, we obtain a general method that given the
specification of a combinatorial species outputs an automaton $\mathcal{A}$
such that $f_{\mathcal{A}}$ is the exponential generating function of the
species.

Finally, in Appendix A we provide effective constructions to show that the
class of generating functions of holonomic tree automata is closed under sum,
Cauchy product, inverse, derivative, integration, forward and backward shift.
We also show that the class of formal tree series recognizable by a holonomic
tree automata is closed under sum and Hadamard product.

###  1.4 Related Work

A power series that satisfies the system (1) in the special case that
$P_{1},\ldots,P_{k}$ are polynomials is called _constructibly differentially
algebraic (CDA)_. Combinatorial interpretations of CDA series were given in
[BR90] (via an automaton-like notion called tree labelling tables) and in
[LV86] (via combinatorial species). However the class of CDA power series does
not include all differentially algebraic series. Indeed, as observed in
[BR90], there are already $D$-finite power series that are not CDA.

Reutnauer [Reu12] introduces and studies a matrix representation of holonomic
sequences. These correspond to the special case of holonomic tree automata
over words, that is, over an alphabet with one nullary and one unary symbol.
Among other things, [Reu12] shows the existence of a minimal representation of
a given sequence that is unique up to change of base.

A Parikh automaton is a non-deterministic finite automaton in which the
acceptance condition is a formula of linear arithmetic that is evaluated on
the Parikh image of the run (i.e., the count of each edge in the run). It is
shown in [BCKN20, CM17] that the multivariate generating series of the
language accepted by an unambiguous Parikh automaton is $D$-finite.

The paper [SMK15] introduces a class of tree automata with registers that have
polynomial updates and proves decidability of equivalence of the formal trees
series they induce. As a corollary, the paper shows decidability of
equivalence of deterministic top-down tree-to-word transducers, resolving a
longstanding open problem. The decision procedure is, however, non-primitive
recursive—the authors show that both equivalence and non-equivalence of formal
tree series are semi-decidable. The semi-decidability of non-equivalence is
obvious, while semi-decidabilty of equivalence follows from the fact that if
two such automata are equivalent then there exists an algebraic inductive
invariant that certifies equivalence and such an invariant can be found by
exhaustive search. We believe that the same invariant technique could be
applied to show decidability of equivalence of holonomic tree automata
(although not necessarily of the associated generating functions).

##  2 From Automata to Differentially Algebraic Functions

In this section, we show that the generating functions of all holonomic tree
automata are differentially algebraic. We start by introducing some notation
that will be used throughout this section. We assume the existence of an
automaton ${\mathcal{A}}=(d,\mu)$ over the alphabet $\Sigma$. We associate $d$
formal power series $f_{1}(x),\ldots,f_{d}(x)$ defined for
$i\in\\{1,\ldots,d\\}$ by
$f_{i}(x):=\sum_{n=0}^{\infty}(\boldsymbol{a}_{n})_{i}\,x^{n}$ where for all
$n\in\mathbb{N}$, $\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in
T_{\Sigma}\\\ |t|=n\end{subarray}}\widetilde{\mu}(t)$. Moreover, we denote by
$\boldsymbol{f}(x)$ the vector of power series
$\begin{bmatrix}f_{1}(x)&\ldots&f_{d}(x)\end{bmatrix}$. In other word, we have
$\boldsymbol{f}(x)=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}x^{n}$ and
$\boldsymbol{f}_{1}(x)=f_{{\mathcal{A}}}(x)$.

######  Definition 1.

Let $f(x)\in\mathbb{Q}[\\![x]\\!]$ be a power series, we say that $f(x)$ is
_differentially algebraic_ , or _D-algebraic_ for short if $f(x)$ satisfies
the differential equation $P(y,y^{\prime},\ldots,y^{(k)})=0$ , where
$P(y_{0},\ldots,y_{k})$ is a polynomial with coefficients in $\mathbb{Q}(x)$.

######  Remark 1.

We can without loss of generality assume that the coefficients of the
polynomial $P$ in definition 1 are in $\mathbb{Q}$. Indeed, as shown in
[vDH19, Proposition 2], for example, $f(x)$ satisfies a polynomial
differential equation with coefficients in $\mathbb{Q}$ if and only if the
transcendence degree
$\mathrm{trdeg}(\mathbb{Q}(\\{f^{(i)}(x):i\in\mathbb{N}\\})/\mathbb{Q})$ is
finite. However, as
$\mathrm{trdeg}(\mathbb{Q}(x)(\\{f^{(i)}(x):i\in\mathbb{N}\\})/\mathbb{Q}(x))$
being finite implies
$\mathrm{trdeg}(\mathbb{Q}(\\{f^{(i)}(x):i\in\mathbb{N}\\})/\mathbb{Q})$ is
also finite, we deduce that $f(x)$ is D-algebraic if and only if $f(x)$
satisfies a polynomial differential equation with coefficients in
$\mathbb{Q}(x)$.

The argument to prove that the generating functions of automata are
differentially algebraic is organised as follows:  (i) we start by stating
some useful properties of $\boldsymbol{f}$, its derivatives and the
coefficient vectors $\boldsymbol{a}_{n}$;  (ii) we show that
$\boldsymbol{f}(x)$ is a component of a solution of a system of differential
equations;  (iii) we show that this system of equations admits a unique vector
of power series solution;  (iv) finally we show that the unique solution is
differentially algebraic.

#### Useful properties.

By definition, we have:

$\boldsymbol{f}(x)=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}x^{n}\qquad\text{with}\qquad\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in
T_{\Sigma}\\\ \|t\|=n\end{subarray}}\widetilde{\mu}(t)\quad\forall
n\in\mathbb{N}$

Notice that the only trees of size $0$ are the nullary function symbols, hence
$\boldsymbol{a}_{0}=\sum_{a\in\Sigma_{0}}\mu(a)$. For all $n>0$, splitting the
sum into the possible shapes that trees can take, we obtain:

$\displaystyle\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}\;\sum_{\begin{subarray}{c}t_{1}\in
T_{\Sigma}\\\
\|t\|=n_{1}\end{subarray}}\ldots\sum_{\begin{subarray}{c}t_{k}\in
T_{\Sigma}\\\
\|t\|=n_{k}\end{subarray}}(\widetilde{\mu}(t_{1})\otimes\ldots\otimes\widetilde{\mu}(t_{k}))\cdot\mu(g)(n,n_{1},\ldots,n_{k})$

Using the bilinearity of the Kronecker product, we obtain:

$\displaystyle\boldsymbol{a}_{n}$
$\displaystyle=\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}\left(\sum_{\begin{subarray}{c}t_{1}\in
T_{\Sigma}\\\
\|t\|=n_{1}\end{subarray}}\widetilde{\mu}(t_{1})\otimes\ldots\otimes\sum_{\begin{subarray}{c}t_{k}\in
T_{\Sigma}\\\
\|t\|=n_{k}\end{subarray}}\widetilde{\mu}(t_{k})\right)\cdot\mu(g)(n,n_{1},\ldots,n_{k})$
$\displaystyle=\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\cdot\mu(g)(n,n_{1},\ldots,n_{k})$
(4)

The property in Equation 4 is very useful as it expresses the coefficient
vectors $\boldsymbol{a}_{n}$ in terms of the previous coefficient vectors
$\boldsymbol{a}_{m}$, $m<n$. We will reuse this property in most sections of
the paper. For instance, by applying this equation to the definition of
$\boldsymbol{f}$, we obtain:

$\displaystyle\boldsymbol{f}(x)-\boldsymbol{a}_{0}$
$\displaystyle=\sum_{n=1}^{\infty}\boldsymbol{a}_{n}x^{n}$
$\displaystyle=\sum_{n=1}^{\infty}\;\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\cdot\mu(g)(n,n_{1},\ldots,n_{k})x^{n}$
$\displaystyle=\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{n=0}^{\infty}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\cdot\mu(g)(n+1,n_{1},\ldots,n_{k})x^{n+1}$

Observe that for any expression $\mathit{fun}(n,n_{1},\ldots,n_{k})$, we have:

$\displaystyle\sum_{n=0}^{\infty}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n\end{subarray}}\;\mathit{fun}(n,n_{1},\ldots,n_{k})=\sum_{n_{1}=0}^{\infty}\ldots\sum_{n_{k}=0}^{\infty}\mathit{fun}(\sum_{i=1}^{k}n_{i},n_{1},\ldots,n_{k})$
(5)

Hence:

$\displaystyle\boldsymbol{f}(x)-\boldsymbol{a}_{0}$
$\displaystyle=x\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{n_{1}=0}^{\infty}\ldots\sum_{n_{k}=0}^{\infty}(\boldsymbol{a}_{n_{1}}x^{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}}x^{n_{k}})\mu(g)(1+\sum_{i=1}^{k}n_{i},n_{1},\ldots,n_{k})$
(6)

Equation 6 is the starting point for building the system of differential
equations satisfied by $f_{\mathcal{A}}(x)$. Indeed, notice that the sums
$\sum_{n_{1}=0}^{\infty}\boldsymbol{a}_{n_{1}}x^{n_{1}}$, …are exactly
$\boldsymbol{f}$. However, this is not sufficient as the term
$\mu(g)(1+\sum_{i=1}^{k}n_{i},n_{1},\ldots,n_{k})$ contains
$n_{1},n_{2}\ldots$ which need to be removed. To do so, we will rely on the
derivatives of $\boldsymbol{f}$.

Let us denote by $\boldsymbol{f}^{(i)}(x)$ the $i$-th derivative of the vector
of power series $\boldsymbol{f}(x)$, that is
$\boldsymbol{f}^{(i)}(x)=\begin{bmatrix}f_{1}^{(i)}(x)&\ldots&f_{d}^{(i)}(x)\end{bmatrix}$.
We also introduce the operator
$\Theta\boldsymbol{f}(x):=x\boldsymbol{f}^{\prime}(x)$. We write
$\Theta^{(0)}\boldsymbol{f}(x)=\boldsymbol{f}(x)$ and for all
$i\in\mathbb{N}$,
$\Theta^{(i)}\boldsymbol{f}(x)=\Theta(\Theta^{(i-1)}\boldsymbol{f})(x)$.

######  Proposition 1.

For all vectors of power series
$\boldsymbol{f}(x)=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}x^{n}$, writing
$0^{0}=1$, we have for all $i\in\mathbb{N}$,
$\Theta^{(i)}\boldsymbol{f}(x)=\sum_{n=0}^{\infty}n^{i}\boldsymbol{a}_{n}x^{n}$.

###### Proof.

We prove this result by induction on $i$. The base case ($i=0$) is trivial. In
the inductive step ($i>0$),
$\Theta^{(i-1)}\boldsymbol{f}(x)=\sum_{n=0}^{\infty}n^{i-1}\boldsymbol{a}_{n}x^{n}$
by inductive hypothesis, hence

$\Theta(\Theta^{(i-1)}\boldsymbol{f})(x)=x(\Theta^{(i-1)}\boldsymbol{f})^{\prime}(x)=x\sum_{n=1}^{\infty}n^{i}\boldsymbol{a}_{n}x^{n-1}=\sum_{n=1}^{\infty}n^{i}\boldsymbol{a}_{n}x^{n}$

As $i>0$, we have $0^{i}=0$ and so
$\Theta^{(i)}\boldsymbol{f}(x)=\sum_{n=0}^{\infty}n^{i}\boldsymbol{a}_{n}x^{n}$.
∎

#### Building the system of differential equations.

By definition, when $g\in\Sigma_{k}$, the coefficients of the matrix $\mu(g)$
are in $\mathbb{Q}_{u}(x_{0},\ldots,x_{k})$, i.e., they are the rational
functions of the form

$\frac{P(x_{0},\ldots,x_{k})}{Q_{0}(x_{0})\cdots Q_{k}(x_{k})}$

where $P\in\mathbb{Q}[x_{0},\ldots,x_{k}]$ and $Q_{i}\in\mathbb{Q}[x_{i}]$ for
$i\in\\{1,\ldots,k\\}$ are polynomials with no nonnegative integer root and
$Q_{0}\in\mathbb{Q}[x_{0}]$ is a polynomial with no positive integer root.
Without loss of generality we can always assume that the coefficients in the
matrix $\mu(g)$ have a common denominator. We cannot make this assumption
throughout all the matrices of the weight function as two symbols may have
different arity, and so their denominators are polynomials in different
numbers of variables. However, the matrices of the weight function associated
to all non-nullary symbols share at least the variable $x_{0}$, meaning that
we can assume that the univariate polynomials associated to $x_{0}$ in all
denominators are the same. In other words, we can assume without loss of
generality that there exist $Q\in\mathbb{Q}[x]$, and $r\in\mathbb{N}$, such
that for all $k\geq 1$, for all $g\in\Sigma_{k}$, there exist some matrices
$\mu_{g,(i_{1},\ldots,i_{k})}\in\mathbb{Q}^{d^{k}\times d}$ for
$i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}$ and polynomials $Q_{g,1},\ldots
Q_{g,k}\in\mathbb{Q}[x]$ such that:

$\displaystyle\mu(g)(x_{0},x_{1},\ldots,x_{k})=\frac{1}{Q(x_{0})}\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}\frac{x_{1}^{i_{1}}\ldots
x_{k}^{i_{k}}}{Q_{g,1}(x_{1})\ldots
Q_{g,k}(x_{k})}\mu_{g,(i_{1},\ldots,i_{k})}$ (7)

Once the weight function is in the shape described in Equation 7, we can build
the system of differential equations satisfied by $\boldsymbol{f}(x)$ as
described in the following proposition.

######  Proposition 2.

Assume that $Q(x)=\sum_{i=0}^{u}c_{i}\,x^{i}$ for some
$c_{0},\ldots,c_{u}\in\mathbb{Q}$ and $u\in\mathbb{N}$. Moreover, for all
$k\geq 1$, for all $g\in\Sigma_{k}$, for all $i\in\\{1,\ldots,k\\}$,

  * •

denote by $\boldsymbol{p}_{g,i}(x)$ the vector of power series
$\sum_{n=0}^{\infty}\boldsymbol{a}_{n}\frac{x^{n}}{Q_{g,i}(n)}$; and

  * •

assume that $Q_{g,i}(x)=\sum_{j=0}^{u}b_{g,i,j}\,x^{j}$ for some
$b_{g,i,0},\ldots,b_{g,i,u}\in\mathbb{Q}$.

The vectors of power series $\boldsymbol{f}(x)$ and $\boldsymbol{p}_{g,i}(x)$
for all $k\geq 1$, $g\in\Sigma_{k}$, $i\in\\{1,\ldots,k\\}$ satisfy the
following system of $d(1+\sum_{k\geq 1}|\Sigma_{k}|\,k)$ differential
equations:

$\displaystyle\sum_{i=0}^{u}c_{i}\Theta^{(i)}\boldsymbol{f}-c_{0}\boldsymbol{a}_{0}=x\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}(\Theta^{(i_{1})}\boldsymbol{p}_{g,1}\otimes\ldots\otimes\Theta^{(i_{k})}\boldsymbol{p}_{g,k})\mu_{g,(i_{1},\ldots,i_{k})}$
(8)
$\displaystyle\boldsymbol{f}=\sum_{j=0}^{u}b_{g,i,j}\Theta^{(j)}\boldsymbol{p}_{g,i}\qquad\forall
k\geq 1,\forall g\in\Sigma_{k},\forall i\in\\{1,\ldots,k\\}$ (9)

###### Proof.

By definition,
$\boldsymbol{p}_{g,i}(x)=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}\frac{x^{n}}{Q_{g,i}(n)}$.
Hence, by Proposition 1, for all $j\in\mathbb{N}$,
$\Theta^{(j)}\boldsymbol{p}_{g,i}(x)=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}\frac{n^{j}x^{n}}{Q_{g,i}(n)}$.
Moreover, as $Q(x)=\sum_{i=0}^{u}c_{i}x^{i}$, we combine all these into the
following sum:

$\displaystyle\sum_{i=0}^{u}c_{i}\Theta^{(i)}\boldsymbol{f}(x)-c_{0}\boldsymbol{a}_{0}$
$\displaystyle=c_{0}\sum_{n=0}^{\infty}\boldsymbol{a}_{n}x^{n}-c_{0}\boldsymbol{a}_{0}+\sum_{i=1}^{u}c_{i}\sum_{n=0}^{\infty}n^{i}\boldsymbol{a}_{n}x^{n}$
$\displaystyle=\sum_{i=0}^{u}c_{i}\sum_{n=0}^{\infty}(n+1)^{i}\boldsymbol{a}_{n+1}x^{n+1}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{i=0}^{u}c_{i}(n+1)^{i}\boldsymbol{a}_{n+1}x^{n+1}$
$\displaystyle=\sum_{n=0}^{\infty}Q(n+1)\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\cdot\mu(g)(n+1,n_{1},\ldots,n_{k})x^{n+1}$
$\displaystyle=\sum_{n=0}^{\infty}Q(n+1)\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\cdot$
$\displaystyle\qquad\frac{1}{Q(n+1)}\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}\frac{n_{1}^{i_{1}}\ldots
n_{k}^{i_{k}}}{Q_{g,1}(n_{1})\ldots
Q_{g,k}(n_{k})}\mu_{g,(i_{1},\ldots,i_{k})}x^{n+1}$
$\displaystyle=\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}\;\sum_{n=0}^{\infty}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\cdot$
$\displaystyle\qquad\qquad\frac{n_{1}^{i_{1}}\ldots
n_{k}^{i_{k}}}{Q_{g,1}(n_{1})\ldots
Q_{g,k}(n_{k})}\mu_{g,(i_{1},\ldots,i_{k})}x^{n+1}$

Once again, applying Equation 5 and the bilinearity of Kronecker product, we
establish the first part of our system of differential equations, that is
Equation 8:

$\displaystyle\sum_{i=0}^{u}c_{i}\Theta^{(i)}\boldsymbol{f}(x)-c_{0}\boldsymbol{a}_{0}$
$\displaystyle=x\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}\;\sum_{n_{1}=0}^{\infty}\ldots\sum_{n_{k}=0}^{\infty}(\frac{n_{1}^{i_{1}}\boldsymbol{a}_{n_{1}}x^{n_{1}}}{Q_{g,1}(n_{1})}\otimes\ldots\otimes\frac{n_{k}^{i_{k}}\boldsymbol{a}_{n_{k}}x^{n_{k}}}{Q_{g,k}(n_{k})})\cdot$
$\displaystyle\qquad\mu_{g,(i_{1},\ldots,i_{k})}$
$\displaystyle=x\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}(\Theta^{(i_{1})}\boldsymbol{p}_{g,1}(x)\otimes\ldots\otimes\Theta^{(i_{k})}\boldsymbol{p}_{g,k}(x))\mu_{g,(i_{1},\ldots,i_{k})}$

We complete the verification of the system of differential equations by
showing, for all $k>0$, all $g\in\Sigma_{k}$ and all $i\in\\{1,\ldots,k\\}$,
that $\boldsymbol{f}(x)$ and $\boldsymbol{p}_{g,i}(x)$ satisfy Equation 9.
Recall that $Q_{g,i}(x)=\sum_{j=0}^{u}b_{g,i,j}x^{j}$. This leads to the
following:

$\displaystyle\sum_{j=0}^{u}b_{g,i,j}\Theta^{(j)}\boldsymbol{p}_{g,i}(x)$
$\displaystyle=\sum_{j=0}^{u}b_{g,i,j}\;\sum_{n=0}^{\infty}n^{j}\boldsymbol{a}_{n}\frac{x^{n}}{Q_{g,i}(n)}$
$\displaystyle=\sum_{n=0}^{\infty}\;\left(\sum_{j=0}^{u}b_{g,i,j}n^{j}\right)\boldsymbol{a}_{n}\frac{x^{n}}{Q_{g,i}(n)}$
$\displaystyle=\sum_{n=0}^{\infty}Q_{g,i}(n)\boldsymbol{a}_{n}\frac{x^{n}}{Q_{g,i}(n)}$
$\displaystyle=\boldsymbol{f}(x)\qed$

#### Uniqueness of solutions.

The system of differential equations given in Proposition 2 is fully defined
by the automaton ${\mathcal{A}}$ and its weight function $\mu$. From
Proposition 2, we showed that the vector of power series $\boldsymbol{f}(x)$
defined at the beginning of the section in conjunction with the vectors of
power series $\boldsymbol{p}_{g,i}(x)$ are solution of this system. We now
show that these vectors were the only possible solution.

######  Proposition 3.

For a given $\overline{\boldsymbol{a}}_{0}\in\mathbb{Q}^{d}$, there exists a
unique power series solution
$(\overline{\boldsymbol{f}}(x),\\{\overline{\boldsymbol{p}}_{g,1}(x),\ldots,\allowbreak\overline{\boldsymbol{p}}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}})$
to the system of differential equations 8 and 9 from Proposition 2 where
$\overline{\boldsymbol{f}}(x)=\sum_{i=0}^{\infty}\overline{\boldsymbol{a}}_{i}x^{i}$.
In other words, if $\overline{\boldsymbol{a}}_{0}=\boldsymbol{a}_{0}$ then
$\overline{\boldsymbol{f}}(x)=\boldsymbol{f}(x)$, where $\boldsymbol{f}(x)$
and $\boldsymbol{a}_{0}$ are those coming from the automaton.

###### Proof.

Note that the equations of 9 give unique relations between the $n^{th}$
coefficient of $\overline{\boldsymbol{f}}(x)$ and the $n^{th}$ coefficient of
$\overline{\boldsymbol{p}}_{g,i}(x)$ for every $i,n.$ In fact, for all $k>0$,
for all $g\in\Sigma_{k}$, for all $i\in\\{1,\ldots,k\\}$, denoting by
$\boldsymbol{d}_{g,i,n}$ the $n^{th}$ coefficient of
$\overline{\boldsymbol{p}}_{g,i}(x)$ (note that $\boldsymbol{d}_{g,i,n}$ is a
vector), we have for all $n\in\mathbb{N}$,

$\displaystyle\sum_{j=0}^{u}b_{g,i,j}\,n^{j}\,\boldsymbol{d}_{g,i,n}=Q_{g,i}(n)\,\boldsymbol{d}_{g,i,n}=\overline{\boldsymbol{a}}_{n}.$
(10)

Therefore, as $Q_{g,i}(n)$ does not vanish for all $n\in\mathbb{N}$, we deduce
from 10 that $\boldsymbol{d}_{g,i,n}$ is uniquely determined by
$\overline{\boldsymbol{a}}_{n}$.

We show by a simple inductive proof on $n$ that every
$\overline{\boldsymbol{a}}_{n}$ are uniquely defined. The base case is trivial
since $\overline{\boldsymbol{a}}_{0}$ is given. In the inductive step ($n>0$),
we know from our inductive hypothesis that all
$\overline{\boldsymbol{a}}_{0},\ldots,\overline{\boldsymbol{a}}_{n-1}$ are
uniquely defined. Thus,
$\overline{\boldsymbol{d}}_{g,i,0},\overline{\boldsymbol{d}}_{g,i,1},\ldots,\overline{\boldsymbol{d}}_{g,i,n-1}$
are also uniquely defined for all $k>0$, for all $g\in\Sigma_{k}$, for all
$i\in\\{1,\ldots,k\\}$.

Note that the $n^{th}$ coefficient of
$\sum_{i=0}^{u}c_{i}\Theta^{(i)}\overline{\boldsymbol{f}}(x)-c_{0}\overline{\boldsymbol{a}}_{0}$
is
$\sum_{i=0}^{u}c_{i}\,n^{i}\,\overline{\boldsymbol{a}}_{n}=Q(n)\overline{\boldsymbol{a}}_{n}$
(since $n>0$). On the other hand, the $n^{th}$ coefficient of the right hand
side of the Equation 8 is the $(n-1)^{th}$ coefficient of

$\sum_{\begin{subarray}{c}k>0\\\
g\in\Sigma_{k}\end{subarray}}\;\sum_{i_{1},\ldots,i_{k}\in\\{0,\ldots,r\\}}(\Theta^{(i_{1})}\overline{\boldsymbol{p}}_{g,1}(x)\otimes\ldots\otimes\Theta^{(i_{k})}\overline{\boldsymbol{p}}_{g,k}(x))\mu_{g,(i_{1},\ldots,i_{k})}$

which is determined uniquely by
$\overline{\boldsymbol{d}}_{g,i,0},\ldots,\overline{\boldsymbol{d}}_{g,i,m}$
with $k>0$, $g\in\Sigma_{k}$, and $i\in\\{1,\ldots,k\\}$. Therefore, since
$Q(n)$ is never zero for all $n\in\mathbb{N}$ by hypothesis,
$\overline{\boldsymbol{a}}_{n}$ is uniquely determined. ∎

#### Existence of a differentially algebraic solution.

We will use the uniqueness of the power series solution to prove that every
entry of this solution is D-algebraic. This is based on a differential version
of the Artin approximation theorem given in [DL84].

######  Theorem 1.

[DL84, Theorem 2.1] Let $S$ be a system of differential polynomials in the
differential variables $y_{1},\ldots,y_{k}$ with coefficients in a field $K$.
Let $(y_{1}(x),\ldots,y_{k}(x))\in K[\\![x]\\!]^{k}$ be a solution of $S$ and
$m\in\mathbb{N}$, then there exists another solution
$(\bar{y}_{1}(x),\ldots,\bar{y}_{k}(x))\in K[\\![x]\\!]^{k}$ such that all
$\bar{y}_{i}(x)$’s are D-algebraic and
$(y_{1}(x),\ldots,y_{k}(x))\equiv(\bar{y}_{1}(x),\ldots,\bar{y}_{k}(x))\pmod{x^{m}}$.

This theorem states that any solution (not necessarily D-algebraic) of a
system of a differential equations can be approximated by a D-algebraic
solution that coincides on the first $m$ coefficients. Since we showed
uniqueness of the power series solutions, we can state our first main result.

######  Theorem 2.

Let ${\mathcal{A}}=(d,\mu)$ be a holonomic tree automaton over an alphabet
$\Sigma$. The generating function $f_{\mathcal{A}}(x)$ is differentially
algebraic.

###### Proof.

From Proposition 2, we know that $\boldsymbol{f}(x)$ and the vectors of power
series $\boldsymbol{p}_{g,i}(x)$ for $k>1$, $g\in\Sigma_{k}$, and
$i\in\\{1,\ldots,k\\}$, are a solution of the system of differential equations
8 and 9. From Theorem 1, we know that there exists another power series
solution $\overline{\boldsymbol{f}}(x)$, $\overline{\boldsymbol{p}}_{g,i}(x)$
for $k>1$, $g\in\Sigma_{k}$, and $i\in\\{1,\ldots,k\\}$ such that all the
power series are D-algebraic and they coincide in particular with the first
coefficients of $\boldsymbol{f}(x)$, i.e.
$\overline{\boldsymbol{a}}_{0}=\boldsymbol{a}_{0}$. From Proposition 3, we
deduce that $\overline{\boldsymbol{f}}(x)=\boldsymbol{f}(x)$ and in particular
$f_{\mathcal{A}}(x)=\overline{\boldsymbol{f}}_{1}(x)$. Since
$\overline{\boldsymbol{f}}_{1}(x)$ is D-algebraic the proof is complete. ∎

##  3 Equivalence of Generating Functions and Formal Tree Series

We are interested in deciding the following two problems:

  * •

(_Equivalence of Formal Tree Series_) Given two automata
${\mathcal{A}}_{1},{\mathcal{A}}_{2}$ over the same alphabet $\Sigma$, does
${\mathcal{A}}_{1}[\\![t]\\!]={\mathcal{A}}_{2}[\\![t]\\!]$ for all $t\in
T_{\Sigma}$?

  * •

(_Equivalence of Generating Functions_) Given two automata
${\mathcal{A}}_{1},{\mathcal{A}}_{2}$, does
$f_{{\mathcal{A}}_{1}}(x)=f_{{\mathcal{A}}_{2}}(x)$?

As previously mentioned, the class of holonomic tree automata is closed under
subtraction, both for formal tree series and generating functions (see
Appendix A for more details). Therefore, we can reduce the respective
equivalence problems to the corresponding zeroness problems:

  * •

(_Zeroness of Formal Tree Series_) Given an automaton ${\mathcal{A}}$, does
${\mathcal{A}}[\\![t]\\!]=0$ for all $t\in T_{\Sigma}$?

  * •

(_Zeroness of Generating Functions_) Given an automaton ${\mathcal{A}}$, does
$f_{{\mathcal{A}}}(x)=0$?

We start by focusing on the zeroness of generating functions. Given a
holonomic tree automaton ${\mathcal{A}}=(d,\mu)$, we use the defining
differential equations of $f_{\mathcal{A}}$ given in Proposition 2 to decide
whether $f_{\mathcal{A}}(x)=0$. Since the system of differential equations has
a unique power series solution by Proposition 3, the zeroness problem can be
reduced to checking whether the system in Proposition 2 remains satisfiable
after adding the equation $f_{1}=0$.

#### Satisfiability of a system of differential equations.

To check the satisfiability of a system of differential algebraic equations,
we rely on a version of the Hilbert Nullstelensatz theorem for differential
ideals [Lan52]. First, we provide some background on differential algebra.

######  Definition 2.

A differential ring $(R,\,^{\prime})$ is a commutative ring with a derivation
${}^{\prime}\\!\\!:R\to R$, that is, a map such that, for all $a,b\in R$,
$(a+b)^{\prime}=a^{\prime}+b^{\prime}$ and
$(ab)^{\prime}=a^{\prime}b+ab^{\prime}$. A differential field is a
differential ring that is a field. For $i>0$, $a^{(i)}$ denotes the $i$-th
order derivative of $a\in R$.

For a variable $y$, write $y^{(\infty)}$ for
$(y,y^{\prime},y^{\prime\prime},\ldots)$ and for the vector
$\mathbf{y}=(y_{1},\ldots,y_{d})$ of variables write $\mathbf{y}^{(\infty)}$
for $(y_{1}^{\infty},\ldots,y_{d}^{\infty})$. Likewise define $y^{(\leq
h)}:=(y,y^{\prime},\ldots,y^{(h)})$ and $\mathbf{y}^{(\leq h)}:=(y_{1}^{(\leq
h)},\ldots,y_{d}^{(\leq h)})$.

######  Definition 3 (Differential polynomials).

Let $R$ be a differential ring and $\mathbf{y}=(y_{1},\ldots,y_{d})$ a vector
of indeterminates. A _differential polynomial_ is a polynomial with
coefficients in $R$ and variables drawn from $\mathbf{y}^{(\infty)}$. We
denote such a polynomial by $P(y_{1},\ldots,y_{d})$. The collection of all
such differential polynomials forms a ring $R[\mathbf{y}^{(\infty)}]$. The
derivation map extends from $R$ to $R[\mathbf{y}^{(\infty)}]$ by defining
$(y_{i}^{(j)})^{\prime}=y_{i}^{(j+1)}$ and lifting $(\cdot)^{\prime}$ to all
of $R[\mathbf{y}^{(\infty)}]$ by linearity and the product rule. Thus
$R[\mathbf{y}^{(\infty)}]$ is a differential ring. The order of a differential
polynomial is the highest order derivative occurring among its variables.

######  Definition 4 (Differential ideals).

Let $R:=K[\mathbf{y}^{(\infty)}]$ be a ring of differential polynomials over a
differential field $K$. An ideal $I\subset R$ is called _a differential ideal_
if $a^{\prime}\in I$ for every $a\in I$. Given a differential polynomial $P$,
write $P^{(\infty)}$ for the set $\\{P,P^{\prime},P^{\prime\prime},\ldots\\}$
of all derivatives of $P$. One can verify that, for every
$P_{1},\ldots,P_{s}\in R$, the ideal $\langle
P_{1}^{(\infty)},\ldots,P_{s}^{(\infty)}\rangle$ is a differential ideal,
which we denote $\langle P_{1},\ldots,P_{s}\rangle^{(\infty)}$.

In our setting, we are mostly interested in the case that $K$ is
$\mathbb{Q}(x)$ or $\overline{\mathbb{Q}}(x)$ and the derivation is the usual
derivative of rational functions. Here $\overline{\mathbb{Q}}$ denotes the
algebraic closure of $\mathbb{Q}$. We can now recall a version of Hilbert
Nullstelensatz theorem for differential ideals.

######  Theorem 3.

[Lan52] Let $P_{1},\ldots,P_{n}$ be differential polynomials in
$\mathbb{Q}(x)[\boldsymbol{y}^{(\infty)}]$, then there exists a tuple of power
series $\boldsymbol{y}(x)$ with coefficients in $\overline{\mathbb{Q}}$ such
that $P_{1}(\boldsymbol{y}(x))=\cdots=P_{n}(\boldsymbol{y}(x))=0$ if and only
if $1\notin\langle P_{1},\ldots,P_{n}\rangle^{(\infty)}$.

Notice here that the coefficients of the power series in $\boldsymbol{y}(x)$
lie in $\overline{\mathbb{Q}}$. We will show that this is not a problem as
Proposition 3 on the uniqueness of solutions does not rely on whether the
coefficients are in $\mathbb{Q}$ or $\overline{\mathbb{Q}}$, as long as the
initial values are the same as the ones of the power series $\boldsymbol{f}$,
$\boldsymbol{p}_{g,i}$, …of the automaton.

Additionally, instead of checking satisfiability over an ideal generated by
infinitely many polynomials there is a bound $B$ for which one can check
satisfiability only over the ideal $\langle P_{1},\ldots,P_{n}\rangle^{(\leq
B)}\coloneqq\langle P_{1}^{(\leq B)},\ldots,P_{n}^{(\leq B)}\rangle$. This
bound was given explicitly in [OPV22].

######  Theorem 4.

[OPV22, Theorem 1] Let $I=\langle P_{1},\ldots,P_{n}\rangle^{(\infty)}$ be a
differential ideal in $\mathbb{Q}(x)[\bf{y}^{(\infty)}]$, then

$\langle P_{1},\ldots,P_{n}\rangle^{(\infty)}\cap\mathbb{Q}(x)=\langle
0\rangle\text{ if and only if }\langle P_{1},\ldots,P_{n}\rangle^{(\leq
B)}\cap\mathbb{Q}(x)=\langle 0\rangle,$

  * •

$B=\max(D^{(\bar{m}+1)2^{m+1}},m+1)$

  * •

$D=\max_{1\leq i\leq n}\deg(P_{i}),$

  * •

$m,\bar{m}$ are respectively the dimension and the codimension of $\langle
P_{1},\ldots,P_{n}\rangle$ in any suitable polynomial ring.

The bound described in this theorem can be computed from the automaton given
as input, which leads to the following decision procedure.

######  Theorem 5 (Zeroness of generating functions).

Let ${\mathcal{A}}=(d,\mu)$ be a holonomic tree automaton over alphabet
$\Sigma$. Assume that the weight function $\mu$ has the form described in
Equation 7 and let $s$ be the maximum of $r$ and the largest degree of the
polynomials $Q$ and $Q_{g,i}$ for all $k>0$, all $g\in\Sigma_{k}$, all
$i\in\\{1,\ldots,k\\}$. Finally, let $M:=d\,(s+2)(1+\sum_{k\geq
1}|\Sigma_{k}|k)+1$, and
$D:=\max\\{k\in\mathbb{N}\mid\Sigma_{k}\neq\emptyset\\}$, and $B:=D^{M2^{M}}$.
Then we have:

$f_{\mathcal{A}}(x)=0\qquad\text{if and only if}\qquad
f_{\mathcal{A}}(x)\equiv 0\pmod{x^{B+1}}$

###### Proof.

By assumption, the weight function $\mu$ has the form described in Equation 7.
Let us rewrite the system of differential equations (8) and (9) as follows:

$\begin{cases}P_{1}(\boldsymbol{f},\\{\boldsymbol{p}_{g,1},\ldots,\boldsymbol{p}_{g,k}\\}_{k>0,g\in\Sigma_{k}})&=0\\\
&\vdots\\\
P_{N}(\boldsymbol{f},\\{\boldsymbol{p}_{g,1},\ldots,\boldsymbol{p}_{g,k}\\}_{k>0,g\in\Sigma_{k}})&=0\end{cases}$
(11)

where $N=d\cdot(1+\sum_{k>0}|\Sigma_{k}|\,k)$. This system is satisfied by the
vector of power series
$\boldsymbol{f}:=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}x^{n}$ associated to
$\mathcal{A}$, where $\boldsymbol{a}_{n}:=\sum_{t:\|t\|=n}\widetilde{\mu}(t)$.
In particular, $\boldsymbol{a}_{0}=\sum_{g\in\Sigma_{0}}\mu(g)$. We define the
polynomials $V_{1},\ldots,V_{d}$ by
$V_{i}:=f_{i}-(\boldsymbol{a}_{0})_{i}-x\,h_{i}$ where
$\boldsymbol{h}=\begin{bmatrix}h_{1}&\ldots&h_{d}\end{bmatrix}$ are fresh
variables.

We now define the following ideal
$I\subseteq\mathbb{Q}(x)[\boldsymbol{f}^{(\leq
u)},\boldsymbol{h},\\{\boldsymbol{p}_{g,1}^{(\leq
s)},\ldots,\boldsymbol{p}_{g,k}^{(\leq s)}\\}_{k>0,g\in\Sigma_{k}}]$:

$I=\langle P_{1},\ldots,P_{n},f_{1},V_{1},\ldots,V_{d}\rangle$

where $s=\max(u,r)$ (see Equation 7). By including $f_{1}$ as a generator of
$I$ we ensure that the power series solution
$\overline{f}_{1},\overline{f}_{2},\ldots$ obtained by applying Theorem 3
satisfies $\overline{f}_{1}(x)=0$. Similarly, by including
$V_{1},\ldots,V_{d}$ as generators of $I$, we ensure that the solution has the
same initial values as $\boldsymbol{f}$, that is:
$\overline{f}_{1}(0)=(\boldsymbol{a}_{0})_{1}$, …,
$\overline{f}_{d}(0)=(\boldsymbol{a}_{0})_{d}$.

The number of variables that appear in the generators of $I$ is
$d(u+2)+d\sum_{k\geq 1}|\Sigma_{k}|\,k(s+1)$, which is bounded by $M$.
Therefore the dimension and the codimension of $I$ ($m$ and $\bar{m}$ in
Theorem 4) are bounded by $M$. Moreover, from Equation (8), we deduce that the
maximal degree of the polynomials $P_{1},\ldots,P_{N}$ are bounded by the
largest arity in $\Sigma$, that is
$\max\\{k\in\mathbb{N}\mid\Sigma_{k}\neq\emptyset\\}=D$.

We can therefore apply Theorem 4 and obtain that:

$I^{(\infty)}\cap\mathbb{Q}(x)=\langle 0\rangle\quad\text{ if and only if
}\quad I^{(\leq B)}\cap\mathbb{Q}(x)=\langle 0\rangle.$

Observe that $I^{(\infty)}\cap\mathbb{Q}(x)=\langle 0\rangle$ is equivalent to
$1\not\in I^{(\infty)}$. Applying Theorem 3, we deduce that $I^{(\leq
B)}\cap\mathbb{Q}(x)=\langle 0\rangle$ if and only if there exist power series
$\overline{\boldsymbol{f}}(x),\overline{\boldsymbol{h}}(x),\\{\overline{\boldsymbol{p}}_{g,1}(x),\ldots,\overline{\boldsymbol{p}}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
with coefficients in $\overline{\mathbb{Q}}$ that are roots of the
differential polynomials $P_{1},\ldots,P_{N},f_{1},V_{1},\ldots,V_{d}$.

Note that by definition of $V_{1},\ldots,V_{d}$, we know that if
$\overline{\boldsymbol{f}}(x),\overline{\boldsymbol{h}}(x),\\{\overline{\boldsymbol{p}}_{g,1}(x),\ldots,\overline{\boldsymbol{p}}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
is a solution of $V_{1},\ldots,V_{n}$ then
$\overline{\boldsymbol{f}}_{i}(x)=(\boldsymbol{a}_{0})_{i}+x\,\overline{\boldsymbol{h}}_{i}(x)$
for all $i\in\\{1,\ldots,d\\}$. In other words,
$\overline{\boldsymbol{f}}(0)=\boldsymbol{a}_{0}$. However, as
$\overline{\boldsymbol{f}}(x),\\{\overline{\boldsymbol{p}}_{g,1}(x),\ldots,\overline{\boldsymbol{p}}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
are also solutions of $P_{1},\ldots,P_{N}$, we deduce from Proposition 3 that
$\overline{\boldsymbol{f}}(x)=\boldsymbol{f}(x)$. As
$\overline{\boldsymbol{f}}(x)$ is also a solution of the polynomial $f_{1}$,
we obtain that $\boldsymbol{f}_{1}(x)=f_{\mathcal{A}}(x)=0$. On the other
hand, we know from Proposition 2 that
$\boldsymbol{f}(x),\\{\boldsymbol{p}_{g,1}(x),\ldots,\boldsymbol{p}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
is a solution of $P_{1},\ldots,P_{N}$ and we can easily build
$\boldsymbol{h}(x)=\boldsymbol{f}(x)-\boldsymbol{a}_{0}$ such that
$\boldsymbol{f}(x),\boldsymbol{h}(x)$ is a solution of the differential
polynomials $V_{1},\ldots,V_{d}$. Thus, if $f_{\mathcal{A}}(x)=0$ then
$\boldsymbol{f}(x),\boldsymbol{h}(x),\\{\boldsymbol{p}_{g,1}(x),\ldots,\boldsymbol{p}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
is a solution of $P_{1},\ldots,P_{N},f_{1},V_{1},\ldots,V_{d}$. This allows us
to obtain the following statement:

$f_{\mathcal{A}}(x)=0\qquad\text{if and only if}\qquad
I^{(\infty)}\cap\mathbb{Q}(x)=\langle 0\rangle$

We conclude the proof by showing that $I^{(\leq B)}\cap\mathbb{Q}(x)=\langle
0\rangle$ is equivalent to $f_{\mathcal{A}}(x)\equiv 0\pmod{x^{B+1}}$.

On the one hand, assume that $I^{(\leq B)}\cap\mathbb{Q}(x)=\langle 0\rangle$.
We have already showed that this implies $f_{\mathcal{A}}(x)=0$, which clearly
implies that $f_{\mathcal{A}}(x)\equiv 0\pmod{x^{B+1}}$.

On the other hand, assume that $f_{\mathcal{A}}(x)\equiv 0\pmod{x^{B+1}}$.
Towards a contradiction, assume that $f_{\mathcal{A}}(x)\neq 0$. Defining
$\boldsymbol{h}(x)=\frac{\boldsymbol{f}(x)-\boldsymbol{a}_{0}}{x}$, we deduce
that
$\boldsymbol{f}(x),\boldsymbol{h}(x),\\{\boldsymbol{p}_{g,1}(x),\ldots,\boldsymbol{p}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
is not a solution of $P_{1},\ldots,P_{N},f_{1},V_{1},\ldots,V_{d}$ and so
$1\in I^{(\leq B)}$. However, by construction and by Proposition 2,
$\boldsymbol{f}(x),\boldsymbol{h}(x),\\{\boldsymbol{p}_{g,1}(x),\ldots,\boldsymbol{p}_{g,k}(x)\\}_{k>0,g\in\Sigma_{k}}$
is a solution of the differential polynomials
$P_{1},\ldots,P_{N},V_{1},\ldots,V_{d}$. Moreover, $I^{(\leq B)}=\langle
f_{1}\rangle^{(\leq B)}+\langle
P_{1},\ldots,P_{N},V_{1},\ldots,V_{d}\rangle^{(\leq B)}$. Therefore, as
$1\in\langle f_{1}\rangle^{(\leq B)}+\langle
P_{1},\ldots,P_{N},V_{1},\ldots,V_{d}\rangle^{(\leq B)}$, we can write:

$1=\sum_{0\leq i\leq B}R_{i}\cdot f_{1}^{(i)}+\sum_{0\leq i\leq
B}\;\sum_{1\leq j\leq N}T_{i}\cdot P_{j}^{(i)}+\sum_{0\leq i\leq
B}\;\sum_{1\leq j\leq d}S_{i}\cdot V_{j}^{(i)}$ (12)

By substituting
$(\boldsymbol{f}(0),\boldsymbol{h}(0),\\{\boldsymbol{p}_{g,1}(0),\ldots,\boldsymbol{p}_{g,k}(0)\\}_{k>0,g\in\Sigma_{k}})$
in (12), we get $1=\sum_{i=1}^{B}\overline{R}_{i}\cdot f_{1}^{(i)}(0)$ where
$\overline{R}_{i}$ is $R_{i}$ after the substitution at
$(\boldsymbol{f}(0),\boldsymbol{h}(0),\\{\boldsymbol{p}_{g,1}(0),\ldots,\boldsymbol{p}_{g,k}(0)\\}_{k>0,g\in\Sigma_{k}})$.
Thus there exists $1\leq i\leq B$ such that $f_{1}^{(i)}(0)\neq 0$ and so
$f_{\mathcal{A}}^{(i)}(0)\neq 0$. This is in contradiction with our hypothesis
$f_{\mathcal{A}}(x)\equiv 0\pmod{x^{B+1}}$. Therefore, our contradiction
assumption does not hold, meaning that $f_{\mathcal{A}}(x)=0$. ∎

With Theorem 5, we obtain a decision procedure for the zeroness of automata
generating functions, consisting of checking whether the $B$ initial values of
the generating function are 0. The decidability of zeroness of generating
functions also gives the dedidability of zeroness of formal tree series, as
shown below.

######  Proposition 4 (Zeroness of formal tree series).

The zeroness problem of formal tree series is decidable.

###### Proof.

Let ${\mathcal{A}}$ be a holonomic tree automaton over $\Sigma$. Since the
formal tree series recognisable by holonomic tree automata are closed under
product (Proposition 11 in Appendix A), we deduce that there exists a
holonomic tree automaton ${\mathcal{A}}^{\prime}$ over $\Sigma$ such that
${\mathcal{A}}^{\prime}[\\![t]\\!]={\mathcal{A}}[\\![t]\\!]^{2}\geq 0$ for all
$t\in T_{\Sigma}$. Since
$f_{{\mathcal{A}}^{\prime}}(x)=\sum_{n=0}^{\infty}\left(\sum_{t:\|t\|=n}{\mathcal{A}}^{\prime}[\\![t]\\!]\right)x^{n}$
and ${\mathcal{A}}^{\prime}[\\![t]\\!]$ is always nonnegative, we deduce that

$f_{{\mathcal{A}}^{\prime}}(x)=0\qquad\text{if and only if}\qquad\forall t\in
T_{\Sigma},{\mathcal{A}}^{\prime}[\\![t]\\!]=0\qquad\text{if and only
if}\qquad\forall t\in T_{\Sigma},{\mathcal{A}}[\\![t]\\!]=0$

As the zeroness problem of generating series is decidable by Theorem 5, the
proof is complete. ∎

######  Corollary 1 (Equivalence).

The equivalence problem of formal tree series and the equivalence problem of
generating functions are decidable.

###### Proof.

Direct from Propositions 4, 2 and 5. ∎

##  4 From Differential Algebraic Functions to Automata

We have shown in Section 2 that the generating functions of holonomic tree
automata are differentially algebraic. Conversely, we are interested in
characterising which differential algebraic power series arise as the
generating function of an automaton.

The main result of this section focuses on the power series that are solutions
of first-order rational systems of differential equations, as defined below.

######  Definition 5.

A _Rational Dynamical System_ is a system of differential equations

$y^{\prime}_{1}=Q_{1}(y_{1},\ldots,y_{k})\quad\ldots\quad
y^{\prime}_{k}=Q_{k}(y_{1},\ldots,y_{k}),$

where $Q_{1},\ldots,Q_{k}$ are rational functions.

We say that a power series $y(x)$ is solution of a rational dynamical system
when there exists a vector $(y_{1}(x),\ldots,y_{k}(x))$ of power series that
satisfy a rational dynamical system
$y^{\prime}_{1}=Q_{1}(y_{1},\ldots,y_{k}),\ldots,y^{\prime}_{k}=Q_{k}(y_{1},\ldots,y_{k})$
such that $y_{1}(x)=y(x)$. In addition, we say that the power series $y(x)$ is
_Rationally Dynamically Algebraic_ (RDA) if $Q_{1},\ldots,Q_{k}$ are defined
at $(y_{1}(0),\ldots,y_{k}(0))$.

The class of power series solution of an RDS is very large as we prove that it
includes all differentially algebraic power series.

######  Proposition 5.

All differentially algebraic power series arise as solutions of rational
dynamical systems.

###### Proof.

Let $y(x)$ be a differentially algebraic power series. Let
$F\in\mathbb{Q}[y^{(\infty)}]$ be a minimal-order differential polynomial such
that $F(y(x))=0$. Let $n$ be the order of $F$. Observe that
$F^{\prime}=y^{(n+1)}S+R$ where $S,R\in\mathbb{Q}[y^{(\leq n)}]$. Moreover we
can assume that $S(y(x),y^{\prime}(x),\ldots,y^{(n)}(x))\neq 0$ as otherwise
the resultant of $F$ and $S$ would give a differential polynomial of order
strictly smaller than $n$ with root $y(x)$. Let us introduce the following
system of differential equations

$\begin{cases}y^{\prime}&=y_{2}\\\ y^{\prime}_{2}&=y_{3}\\\ &\vdots\\\
y_{n-1}^{\prime}&=y_{n}\\\
y_{n}^{\prime}&=\frac{R(y,y_{2}\ldots,y_{n})}{S(y,y_{2}\ldots,y_{n})}\end{cases}$
(13)

We directly have that $(y(x),y^{\prime}(x),\ldots,y^{(n)}(x))$ is solution of
the system (13) which allows us to conclude. ∎

As previously mentioned, the main result of this section shows that every RDA
power series is the generating function of a holonomic tree automaton.
However, as the transformation from rational dynamical systems to automata is
quite complex, we start by exhibiting a transformation for D-finite power
series, followed by one for CDA power series, before finally treating the
whole class of RDA power series.

######  Proposition 6 (D-finite power series).

For all D-finite power series $f(x)$, there exists a holonomic tree automaton
${\mathcal{A}}$ such that $f_{\mathcal{A}}(x)=f(x)$.

###### Proof.

By definition, if $f(x)=\sum^{\infty}_{n=0}a_{n}x^{n}$ then its series
$(a_{n})_{n=0}^{\infty}$ of coefficients satisfies a polynomial recurrence

$Q_{0}(n)a_{n}+Q_{1}(n)a_{n-1}+\ldots+Q_{k}(n)a_{n-k}=0\qquad(n\geq k)$

such that for all $n\geq k$, $Q_{0}(n)\neq 0$. We build the automaton
${\mathcal{A}}=(d,\mu)$ over an alphabet $\Sigma=\\{\sigma_{0},\sigma_{1}\\}$
such that for all $n\in\mathbb{N}$,

$\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\begin{bmatrix}a_{n}&\ldots&a_{n+k-1}\end{bmatrix}$

To do so, we consider $d=k$ with the following weight function:

$\mu(\sigma_{0})=\begin{bmatrix}a_{0}&\ldots&a_{k-1}\end{bmatrix}\qquad\text{
and }\qquad\mu(\sigma_{1})(x_{0},x_{1})=\begin{bmatrix}\boldsymbol{0}_{1\times
d-1}&\frac{Q_{k}(x_{1}+k-1)}{Q_{0}(x_{1}+k-1)}\\\
I_{d-1}&\begin{matrix}\frac{Q_{k-1}(x_{1}+k-1)}{Q_{0}(x_{1}+k-1)}\\\ \vdots\\\
\frac{Q_{1}(x_{1}+k-1)}{Q_{0}(x_{1}+k-1)}\end{matrix}\end{bmatrix}$

Let us show the desired property by induction on $n$. The base case ($n=0$)
being trivial, we focus on the induction step $n>0$. In such a case, denoting
$\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)$ for all $n\in\mathbb{N}$, we obtain
from Equation 4 that
$\boldsymbol{a}_{n}=\boldsymbol{a}_{n-1}\mu(\sigma)(n+1,n)$. By the induction
hypothesis, we deduce that
$\boldsymbol{a}_{n-1}=\begin{bmatrix}a_{n-1}&\ldots&a_{n+k-2}\end{bmatrix}$
and so:

$\displaystyle\boldsymbol{a}_{n}$
$\displaystyle=\begin{bmatrix}a_{n-1}&\ldots&a_{n+k-2}\end{bmatrix}\mu(\sigma)(n+1,n)$
$\displaystyle=\begin{bmatrix}a_{n}&\ldots&a_{n+k-2}&\frac{1}{Q_{0}(n+k-1)}\sum_{i=0}^{k-1}Q_{k-i}(n+k-1)a_{n-1+i}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}a_{n}&\ldots&a_{n+k-2}&a_{n+k-1}\end{bmatrix}\qed$

For D-finite power series, the construction of the automaton consists of
storing consecutive values of the recurrence in states of our automaton, i.e.
$\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\begin{bmatrix}a_{n}&\ldots&a_{n+k-1}\end{bmatrix}$.
For CDA power series, i.e., power series defined by a rational dynamical
system in $y_{1},\ldots,y_{k}$ with polynomials instead of rational functions,
the intuition is similar. The values of the states of the automaton contain
the current coefficients of the solution $y_{1}(x),\ldots,y_{k}(x)$. In other
words, we have $\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\begin{bmatrix}a_{n,1}&\ldots&a_{n,k}&1\end{bmatrix}$
where $a_{n,i}$ is the $n^{th}$ coefficient of $y_{i}(x)$. This similarity is
explained by the fact that the rational dynamical system for which a D-finite
power series $f(x)$ is solution can intuitively be obtained by introducing new
variables $f_{1},\ldots,f_{k-1}$ for each derivative
$f^{(1)},\ldots,f^{(k-1)}$ (and possibly additional variables). The current
values of each $f_{1},\ldots,f_{k-1}$ will thus correspond to coefficients
$a_{n+1},\ldots,a_{n+k-1}$ of the recurrence relation.

######  Proposition 7 (CDA power series).

For all CDA power series $f(x)$, there exists a holonomic tree automaton
${\mathcal{A}}$ such that $f_{\mathcal{A}}(x)=f(x)$.

###### Proof.

By definition, there is a system of differential equations of the form

$y_{1}^{\prime}=P_{1}(y_{1},\ldots,y_{k})\quad\ldots\quad
y_{k}^{\prime}=P_{k}(y_{1},\ldots,y_{k})$

and $(y_{1}(x),\ldots,y_{k}(x))$ power series solution of this system such
that $y_{1}(x)=f(x)$ and for all $i\in\\{1,\ldots,k\\}$,
$P_{i}\in\mathbb{Q}[y_{1},\ldots,y_{k}]$.

Let us denote by $r$ the maximal degree of all polynomials
$P_{1},\ldots,P_{k}$. As such, each $P_{j}$ has the form:

$P_{j}(y_{1},\ldots,y_{k})=\sum_{\ell=0}^{r}\;\sum_{i_{1},\ldots,i_{\ell}\in\\{1,\ldots,k\\}}\alpha_{(i_{1},\ldots,i_{\ell}),j}\;y_{i_{1}}\ldots
y_{i_{\ell}}\,,$

where the all coefficients $\alpha_{(i_{1},\ldots,i_{\ell}),j}$ are in
$\mathbb{Q}$. Note that the given system of equations can be transformed into:

$\Theta y_{1}=xP_{1}(y_{1},\ldots,y_{k})\quad\ldots\quad\Theta
y_{k}=xP_{k}(y_{1},\ldots,y_{k})$

Since $(y_{1}(x),\ldots,y_{k}(x))$ are power series, if we denote
$y_{i}(x)=\sum_{n=0}^{\infty}a_{n,i}\,x^{n}$ for all $i\in\\{1,\ldots,k\\}$,
then we deduce that the coefficients of the power series satisfy the following
recurrence relations: For all $j\in\\{1,\ldots,k\\}$, for all $n\geq 1$,

$n\,a_{n,j}=\sum_{\ell=0}^{r}\;\sum_{(i_{1},\ldots,i_{\ell})\in\\{1,\ldots,k\\}^{*}}\;\sum_{\begin{subarray}{c}n_{1}+\ldots+n_{\ell}=n-1\\\
n_{1},\ldots,n_{\ell}\in\mathbb{N}\end{subarray}}\;\alpha_{(i_{1},\ldots,i_{\ell}),j}\,a_{n_{1},i_{1}}\ldots
a_{n_{\ell},i_{\ell}}$

Let us build the automaton ${\mathcal{A}}$ over the alphabet
$\Sigma=\\{\varepsilon,\sigma,g_{1},\ldots,g_{r}\\}$ with $\varepsilon$ being
a nullary symbol, $\sigma$ being a unary symbol and for all
$i\in\\{1,\ldots,r\\}$, $g_{i}$ is a $i$-ary symbol. Intuitively, each $g_{i}$
with $i\geq 1$ will represent all the monomials of degree $i>0$. The symbol
$\sigma$ will represent the constants. We now build the weight function $\mu$
of the automaton ${\mathcal{A}}$ such that for all $n\in\mathbb{N}$,

$\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\begin{bmatrix}a_{n,1}&\ldots&a_{n,k}&1\end{bmatrix}$

To do so, our automaton ${\mathcal{A}}$ must have dimension $k+1$ and weight
function defined by:

  * •

$\mu(\varepsilon)=\begin{bmatrix}a_{0,1}&\ldots&a_{0,k}&1\end{bmatrix}$

  * •

for all $\forall\ell\in\\{1,\ldots,r\\}$, for all
$i_{1},\ldots,i_{\ell},j\in\\{1,\ldots,k+1\\}$,

$\mu(g_{\ell})_{(i_{1},\ldots,i_{\ell}),j}(x_{0},\ldots,x_{\ell})=\left\\{\begin{array}[]{lr}\frac{\alpha_{(i_{1},\ldots,i_{\ell}),j}}{x_{0}}&\text{if
}\forall i_{1},\ldots,i_{\ell},j\in\\{1,\ldots,k\\}\\\
0&\text{otherwise}\end{array}\right.$

  * •

for all $i,j\in\\{1,\ldots,k+1\\}$,

$\mu(\sigma)_{i,j}(x_{0},x_{1})=\left\\{\begin{array}[]{lr}\frac{\alpha_{(),j}}{x_{0}}&\text{if
}i=k+1,j\leq k\\\ 1&\text{if }i=j=k+1\\\ 0&\text{otherwise}\end{array}\right.$

We prove the desired property by induction on $n$. The base case $n=0$ being
trivial, we focus on the induction step ($n>0$). Denoting
$\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)$ for all $n\in\mathbb{N}$, we know
from Equation 4 and from our induction hypothesis that for all $n\geq 1$,

$\displaystyle\boldsymbol{a}_{n}$
$\displaystyle=\sum_{\begin{subarray}{c}\ell>0\\\
g\in\Sigma_{\ell}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{\ell}\in\mathbb{N}\\\
n_{1}+\ldots+n_{\ell}=n-1\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{\ell}})\cdot\mu(g)(n,n_{1},\ldots,n_{\ell})$
$\displaystyle=\sum_{\begin{subarray}{c}\ell>0\\\
g\in\Sigma_{\ell}\end{subarray}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{\ell}\in\mathbb{N}\\\
n_{1}+\ldots+n_{\ell}=n-1\end{subarray}}(\begin{bmatrix}a_{n_{1},1}&\ldots&a_{n_{1},k}&1\end{bmatrix}\otimes\ldots\otimes\begin{bmatrix}a_{n_{\ell},1}&\ldots&a_{n_{\ell},k}&1\end{bmatrix})\cdot\mu(g)(n,n_{1},\ldots,n_{\ell})$

Therefore, by definition of $\mu$, we have for $j\in\\{1,\ldots,k\\}$,

$\displaystyle\boldsymbol{a}_{n,j}$
$\displaystyle=\boldsymbol{a}_{n-1,k+1}\frac{\alpha_{(),j}}{n}+\sum_{\ell=1}^{r}\sum_{\begin{subarray}{c}n_{1},\ldots,n_{\ell}\in\mathbb{N}\\\
n_{1}+\ldots+n_{\ell}=n-1\end{subarray}}\sum_{(i_{1},\ldots,i_{\ell})\in\\{1,\ldots,k\\}^{*}}a_{n_{1},i_{1}}\ldots
a_{n_{\ell},i_{\ell}}\frac{\alpha_{(i_{1},\ldots,i_{\ell}),j}}{n}$
$\displaystyle=\sum_{\ell=0}^{r}\sum_{\begin{subarray}{c}n_{1},\ldots,n_{\ell}\in\mathbb{N}\\\
n_{1}+\ldots+n_{\ell}=n-1\end{subarray}}\sum_{(i_{1},\ldots,i_{\ell})\in\\{1,\ldots,k\\}^{*}}a_{n_{1},i_{1}}\ldots
a_{n_{\ell},i_{\ell}}\frac{\alpha_{(i_{1},\ldots,i_{\ell}),j}}{n}$
$\displaystyle=a_{n,j}$

Furthermore, we also have that:

$\boldsymbol{a}_{n,k+1}=\boldsymbol{a}_{n-1,k+1}\mu(\sigma)_{k+1,k+1}(n,n-1)=1$

This allows us to conclude the proof that for all $n\in\mathbb{N}$,
$\boldsymbol{a}_{n}=\begin{bmatrix}a_{n,1}&\ldots&a_{n,k}&1\end{bmatrix}$, and
so $f_{\mathcal{A}}(x)=y_{1}(x)=f(x)$. ∎

######  Example 4.

As an example, take the function $y_{1}(x)=\frac{1}{\cos(x)}$ and
$y_{2}(x)=\tan(x)$. They satisfy the system of differential equations:

$\left\\{\begin{array}[]{l}y^{\prime}_{1}=y_{1}\,y_{2}\\\
y^{\prime}_{2}=1+y_{2}^{2}\end{array}\right.$

It was shown that in [Sta80, Example 2.5] that $y_{1}(x)$ is not D-finite. Let
us build the corresponding holonomic tree automaton based on the proof of
Proposition 7. The maximal degree $r$ of the polynomials is $2$ but there is
no monomial of degree 1. Therefore, we consider the alphabet
$\Sigma=\\{\varepsilon,\sigma,g_{2}\\}$ (no need for the symbol $g_{1}$
representing the monomial of degree 1). Since we only have two variables,
$y_{1},y_{2}$, the dimension of our automaton is 3. As $y_{1}(0)=1$ and
$y_{2}(0)=0$, the weight function is defined as follows:

$\mu(\varepsilon)=\begin{bmatrix}1&0&1\end{bmatrix}\qquad\mu(\sigma)(x_{0},x_{1})=\begin{bmatrix}0&0&0\\\
0&0&0\\\
0&\frac{1}{x_{0}}&1\end{bmatrix}\qquad\mu(g_{2})(x_{0},x_{1},x_{2})=\begin{bmatrix}0&0&0\\\
\frac{1}{x_{0}}&0&0\\\ \boldsymbol{0}_{1\times 2}&\boldsymbol{0}_{1\times
2}&\boldsymbol{0}_{1\times 2}\\\ 0&\frac{1}{x_{0}}&1\\\
\boldsymbol{0}_{1\times 4}&\boldsymbol{0}_{1\times 4}&\boldsymbol{0}_{1\times
4}\end{bmatrix}$

The construction for RDA power series will take a similar approach, for
instance by splitting the rational functions into their monomials. However, to
handle the presence of polynomials in both denominators and numerators, we
will first transform the system to reduce its maximal degree to be at most 2.
This is done in particular by introducing new variables whose values will also
appear in the states of the automaton, thus increasing the dimension of the
automaton. Another change in the construction is that, instead of keeping the
current values, the automaton keeps the forward-shifted values of each
variable and only keep the current value of the target function. In other
words, we seek to maintain the invariant

$\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\begin{bmatrix}a_{n,1}&a_{n+1,1}&a_{n+1,2}&\ldots&a_{n+1,k}&b_{n+1,1}&\ldots&b_{n+1,s}&1\end{bmatrix}$

where the $a_{n,i}$ is the $n$-th coefficient of the power series $y_{i}(x)$
and the $b_{n,i}$ are auxiliary variables introduced during the transformation
of the system.

######  Theorem 6 (RDA power series).

For all RDA power series $f(x)$, there exists a holonomic tree automaton
${\mathcal{A}}$ such that $f_{\mathcal{A}}(x)=f(x)$.

###### Proof.

By definition, there exists a rational dynamical system of the form

$y_{1}^{\prime}=\frac{P_{1}(y_{1},\ldots,y_{k})}{Q_{1}(y_{1},\ldots,y_{k})}\quad\ldots\quad
y_{k}^{\prime}=\frac{P_{k}(y_{1},\ldots,y_{k})}{Q_{k}(y_{1},\ldots,y_{k})}$

and $(y_{1}(x),\ldots,y_{k}(x))$ power series solution of this system such
that $f(x)=y_{1}(x)$ and for all $i\in\\{1,\ldots,k\\}$,
$P_{i},Q_{i}\in\mathbb{Q}[y_{1},\ldots,y_{k}]$ and
$Q_{i}(y_{1}(0),\ldots,y_{k}(0))\neq 0$.

Let us denote by $r$ the maximal degree of all polynomials
$P_{1},Q_{1},\ldots,P_{k},Q_{k}$. As such, each $P_{j}$ and $Q_{j}$ are of the
form:

$\begin{array}[]{c}P_{j}(y_{1},\ldots,y_{k})=\sum_{\ell=0}^{r}\;\sum_{(i_{1},\ldots,i_{\ell})\in\\{1,\ldots,k\\}^{*}}\;\alpha_{(i_{1},\ldots,i_{\ell}),j}\,y_{i_{1}}\ldots
y_{i_{\ell}}\\\\[5.69054pt]
Q_{j}(y_{1},\ldots,y_{k})=\sum_{\ell=0}^{r}\;\sum_{(i_{1},\ldots,i_{\ell})\in\\{1,\ldots,k\\}^{*}}\;\beta_{(i_{1},\ldots,i_{\ell}),j}\,y_{i_{1}}\ldots
y_{i_{\ell}}\end{array}$

where all the coefficients $\alpha_{(i_{1},\ldots,i_{\ell}),j}$ and
$\beta_{(i_{1},\ldots,i_{\ell}),j}$ are in $\mathbb{Q}$. Note that the given
system of equations can be transformed into:

$Q_{1}(y_{1},\ldots,y_{k})\Theta
y_{1}=xP_{1}(y_{1},\ldots,y_{k})\quad\ldots\quad
Q_{k}(y_{1},\ldots,y_{k})\Theta y_{k}=xP_{k}(y_{1},\ldots,y_{k})$ (14)

We introduce several new variables in order to transform the system of
equations 14 into a set of equations of degree 2. To start, we introduce
variables $z_{1},\ldots,z_{k},w_{1},\ldots,w_{k}$ and transform 14 to the
equivalent system:

$\left\\{\begin{array}[]{lcl}z_{1}\Theta y_{1}=x\,w_{1}&\ldots&z_{k}\Theta
y_{k}=x\,w_{k}\\\
z_{1}=Q_{1}(y_{1},\ldots,y_{k})&\ldots&z_{k}=Q_{k}(y_{1},\ldots,y_{k})\\\
w_{1}=P_{1}(y_{1},\ldots,y_{k})&\ldots&w_{k}=P_{k}(y_{1},\ldots,y_{k})\\\
\end{array}\right.$ (15)

Then, for each monomial $y_{i_{1}}\ldots y_{i_{\ell}}$ in
$Q_{j}(y_{1},\ldots,y_{k})$ and $P_{j}(y_{1},\ldots,y_{k})$ with $\ell>2$, we
introduce fresh variables $t_{1},\ldots,t_{\ell}$ to split the equations
$z_{j}=Q_{j}(y_{1},\ldots,y_{k})$ and $w_{j}=P_{j}(y_{1},\ldots,y_{k})$ into
an equivalent system of equations of degree at most 2 as follows:

$t_{1}=y_{i_{1}}t_{2}\qquad t_{2}=y_{i_{2}}t_{3}\qquad\ldots\qquad
t_{\ell-1}=y_{\ell-1}t_{\ell}\qquad t_{\ell}=y_{\ell}$

By applying this transformation to every monomial in every polynomial
$Q_{j}(y_{1},\ldots,y_{k})$ and $P_{j}(y_{1},\ldots,y_{k})$ and after renaming
the newly introduced variables, we deduce that the set of solutions of system
(15) in variables $y_{1},\ldots,y_{k}$ equals the set of solutions in
$y_{1},\ldots,y_{k}$ of the following system:

$\left\\{\begin{array}[]{c}z_{1}\Theta y_{1}=x\,w_{1}\quad\ldots\quad
z_{k}\Theta y_{k}=x\,w_{k}\\\
z_{1}=R_{1}(y_{1},\ldots,y_{k},t_{1},\ldots,t_{s})\quad\ldots\quad
z_{k}=R_{k}(y_{1},\ldots,y_{k},t_{1},\ldots,t_{s})\\\
w_{1}=S_{1}(y_{1},\ldots,y_{k},t_{1},\ldots,t_{s})\quad\ldots\quad
w_{k}=S_{k}(y_{1},\ldots,y_{k},t_{1},\ldots,t_{s})\\\
t_{1}=T_{1}(y_{1},\ldots,y_{k},t_{2},\ldots,t_{s})\quad
t_{2}=T_{2}(y_{1},\ldots,y_{k},t_{3},\ldots,t_{s})\quad\ldots\quad
t_{s}=T_{s}(y_{1},\ldots,y_{k})\end{array}\right.$ (16)

where $R_{1},S_{1}\ldots,R_{k},S_{k}$ and $T_{1},\ldots,T_{s}$ are polynomials
of degree at most 2. Moreover in $T_{1},\ldots,T_{s}$, all monomials of degree
2 have one variable from $\\{y_{1},\ldots,y_{k}\\}$ and one variable from
$\\{t_{1},\ldots,t_{s}\\}$.

Since the power series $(y_{1}(x),\ldots,y_{k}(x))$ are solutions of the
initial system (14), we also deduce the existence of power series
$z_{1}(x),\ldots,z_{k}(x),w_{1}(x),\ldots,w_{k}(x),t_{1}(x),\ldots,t_{s}(x)$
that, together with $(y_{1}(x),\ldots,y_{k}(x))$, form a solution of the
system system (16). Let us denote by $y_{n,i}$ (resp.
$z_{n,i},w_{n,i},t_{n,i}$), $n\in\mathbb{N}$ the coefficients of the power
series $y_{i}(x)$ (resp. $z_{i}(x),w_{i}(x),t_{i}(x)$). From (16) we deduce
that these coefficients satisfy the following relations:

  * •

For all $n\geq 1$, for all $j\in\\{1,\ldots,k\\}$,

$\displaystyle\sum_{\ell=0}^{n+1}z_{\ell,j}(n+1-\ell)y_{n+1-\ell,j}=w_{n,j}$
$\displaystyle\Longleftrightarrow\quad$ $\displaystyle
z_{0,j}(n+1)y_{n+1,j}+\sum_{\ell=1}^{n}z_{\ell,j}(n+1-\ell)y_{n+1-\ell,j}=w_{n,j}$
$\displaystyle\Longleftrightarrow\quad$ $\displaystyle
y_{n+1,j}=\frac{1}{z_{0,j}(n+1)}\left(w_{n,j}-\sum_{\ell=1}^{n}z_{\ell,j}(n+1-\ell)y_{n+1-\ell,j}\right)$
$\displaystyle\Longleftrightarrow\quad$ $\displaystyle
y_{n+1,j}=\frac{1}{z_{0,j}(n+1)}\left(w_{n,j}-\sum_{\ell=0}^{n-1}z_{\ell+1,j}(n-\ell)y_{n-\ell,j}\right)$

By the assumption that $Q_{i}(y_{1}(0),\ldots,y_{k}(0))\neq 0$ for all
$i\in\\{1,\ldots,k\\}$ we deduce from (15) that $z_{0,j}\neq 0$ for all
$j\in\\{1,\ldots,k\\}$. Introducing new variables
$\overline{z}_{n,j}=z_{n+1,j}$, $\overline{y}_{n,j}=y_{n+1,j}$ and
$\overline{w}_{n,j}=w_{n+1,j}$, for all $j\in\\{1,\ldots,k\\}$ and $n\geq 1$,
we obtain :

$\overline{y}_{n,j}=\frac{1}{z_{0,j}(n+1)}\left(\overline{w}_{n-1,j}-\sum_{\ell=0}^{n-1}\overline{z}_{\ell,j}(n-\ell)\overline{y}_{n-1-\ell,j}\right)$
(17)

Notice that the shape of this equation is reminiscent of Equation 4 and they
will intuitively correspond to the application of several symbols of the
alphabet $\Sigma$: the term $\overline{w}_{n-1,j}$ will correspond to the
application of a unary symbol whereas the term
$\sum_{\ell=0}^{n-1}\overline{z}_{\ell,j}(n-\ell)\overline{y}_{n-1-\ell,j}$
will correspond to the application of a binary symbol.

  * •

Let us denote
$\Gamma=\\{w_{i},y_{i},z_{i}\\}_{i=1}^{k}\cup\\{t_{1},\ldots,t_{s}\\}$. We
show by induction on $s-j$ that for all $j\in\\{1,\ldots,s\\}$, for all $n\geq
1$,

$\overline{t}_{n,j}=A(n)+\sum_{h\in\Gamma}B_{h}(n,n-1)\overline{h}_{n-1}+\sum_{h,g\in\Gamma}\sum_{\ell=0}^{n-1}C_{h,g}(n,\ell,n-1-\ell)\,\overline{h}_{\ell}\,\overline{g}_{n-1-\ell}$
(18)

where $A\in\mathbb{Q}_{u}(x_{0})$, $B_{h}\in\mathbb{Q}_{u}(x_{0},x_{1})$ and
$C_{h,g}\in\mathbb{Q}_{u}(x_{0},x_{1},x_{2})$

In the base case ($s=j$), we know that $t_{s}=T_{s}(y_{1},\ldots,y_{k})$.
Moreover, we also know that $T_{s}$ is of degree at most 2 and all monomials
of degree 2 must have a variable from $\\{t_{1},\ldots,t_{s}\\}$. In other
words, $T_{s}$ is of degree at most 1. Therefore, for all $n\geq 1$,

$\displaystyle\overline{t}_{n,s}$
$\displaystyle=\alpha+\sum_{j=1}^{k}\beta_{j}\overline{y}_{n,j}$
$\displaystyle=\alpha+\sum_{j=1}^{k}\frac{\beta_{j}}{z_{0,j}(n+1)}\left(\overline{w}_{n-1,j}-\sum_{\ell=0}^{n-1}\overline{z}_{\ell,j}(n-\ell)\overline{y}_{n-1-\ell,j}\right)$
$\displaystyle=\alpha+\sum_{j=1}^{k}\frac{\beta_{j}\,\overline{w}_{n-1,j}}{z_{0,j}(n+1)}-\sum_{j=1}^{k}\sum_{\ell=0}^{n-1}\frac{(n-\ell)\beta_{j}}{z_{0,j}(n+1)}\overline{z}_{\ell,j}\overline{y}_{n-1-\ell,j}$

Hence the result holds.

In the inductive step ($s>j$), we know that
$t_{j}=T_{j}(y_{1},\ldots,y_{k},t_{j+1},\ldots,t_{s})$ with $T_{j}$ being of
degree at most 2 and that all monomials of degree 2 must have a variable from
$\\{t_{1},\ldots,t_{s}\\}$ and one from $\\{y_{1},\ldots,y_{k}\\}$. For a
monomial of degree 1, i.e. $\alpha\,u$, as
$u\in\\{y_{1},\ldots,y_{k},t_{j+1},\ldots,t_{s}\\}$ and by Equation 17 and our
inductive hypothesis (18) on each $t_{j+1},\ldots,t_{s}$, we have the equation
$(\alpha\,u)_{n+1}=\alpha\overline{u}_{n}$, which already has the desired
form.

We now focus on the monomials of degree 2. Assume that $\alpha uv$ is a
monomial of $T_{j}$ with
$u,v\in\\{y_{1},\ldots,y_{k},t_{j+1},\ldots,t_{s}\\}$. Then we have for all
$n\geq 1$,

$\displaystyle(\alpha\,u\,v)_{n+1}$
$\displaystyle=\alpha\sum_{\ell=0}^{n+1}u_{\ell}\,v_{n+1-\ell}$ (19)
$\displaystyle=\alpha\,u_{0}\,v_{n+1}+\alpha\,u_{n+1}\,v_{0}+\alpha\sum_{\ell=1}^{n}u_{\ell}\,v_{n+1-\ell}$
$\displaystyle=\alpha\,u_{0}\,\overline{v}_{n}+\alpha\,\overline{u}_{n}\,v_{0}+\alpha\sum_{\ell=0}^{n-1}\overline{u}_{\ell}\,\overline{v}_{n-1-\ell}$
(20)

By Equation 17 and by our inductive hypothesis (18) on each
$t_{j+1},\ldots,t_{s}$, we deduce that:

$\displaystyle\overline{u}_{n}$
$\displaystyle=A(n)+\sum_{h\in\Gamma}B_{h}(n,n-1)\overline{h}_{n-1}+\sum_{h,g\in\Gamma}\sum_{\ell=0}^{n-1}C_{h,g}(n,\ell,n-1-\ell)\,\overline{h}_{\ell}\,\overline{g}_{n-1-\ell}$
$\displaystyle\overline{v}_{n}$
$\displaystyle=D(n)+\sum_{h\in\Gamma}E_{h}(n,n-1)\overline{h}_{n-1}+\sum_{h,g\in\Gamma}\sum_{\ell=0}^{n-1}F_{h,g}(n,\ell,n-1-\ell)\,\overline{h}_{\ell}\,\overline{g}_{n-1-\ell}$

for some $A,D\in\mathbb{Q}_{u}(x_{0})$,
$B_{h},E_{h}\in\mathbb{Q}_{u}(x_{0},x_{1})$ and
$C_{h,g},F_{h,g}\in\mathbb{Q}_{u}(x_{0},x_{1},x_{2})$. Therefore, by combining
these two equations with Equation 20, we obtain that the monomial
$(\alpha\,u\,v)_{n+1}$ has the desired form.

  * •

For all $j\in\\{1,\ldots,k\\}$, for all $n\geq 1$, since
$z_{j}=R_{j}(y_{1},\ldots,y_{k},t_{1},\ldots,t_{s})$ and
$w_{j}=S_{j}(y_{1},\ldots,y_{k},\allowbreak t_{1},\ldots,t_{s})$, where
$R_{1},S_{1},\ldots,R_{k},S_{k}$ are also polynomials of degree at most 2, we
can apply the same proof as in the previous case (the $\overline{t}_{n,j}$s)
to show that both $\overline{w}_{n,j}$ and $\overline{z}_{n,j}$ are of the
form:

$A(n)+\sum_{h\in\Gamma}B_{h}(n,n-1)\overline{h}_{n-1}+\sum_{h,g\in\Gamma}\sum_{\ell=0}^{n-1}C_{h,g}(n,\ell,n-1-\ell)\,\overline{h}_{\ell}\,\overline{g}_{n-1-\ell}$

with $A\in\mathbb{Q}_{u}(x_{0})$, $B_{h}\in\mathbb{Q}_{u}(x_{0},x_{1})$ and
$C_{h,g}\in\mathbb{Q}_{u}(x_{0},x_{1},x_{2})$.

To summarize, we have proved that for all $n\geq 1$, the coefficients
$\overline{y}_{n,i}$, $\overline{z}_{n,i}$, $\overline{w}_{n,i}$ and
$\overline{t}_{n,i}$ are all of the form

$A(n)+\sum_{h\in\Gamma}B_{h}(n,n-1)\overline{h}_{n-1}+\sum_{h,g\in\Gamma}\sum_{\ell=0}^{n-1}C_{h,g}(n,\ell,n-1-\ell)\,\overline{h}_{\ell}\,\overline{g}_{n-1-\ell}$

with $\Gamma=\\{w_{i},y_{i},z_{i}\\}_{i=1}^{k}\cup\\{t_{1},\ldots,t_{s}\\}$,
$A\in\mathbb{Q}_{u}(x_{0})$, $B_{h}\in\mathbb{Q}_{u}(x_{0},x_{1})$ and
$C_{h,g}\in\mathbb{Q}_{u}(x_{0},x_{1},x_{2})$.

From this point the construction of our automaton is straightforward. First,
we will consider an automaton ${\mathcal{A}}=(d,\mu)$ of dimension $d=2+3k+s$
over the alphabet $\Sigma=\\{\varepsilon,\sigma_{1},\sigma_{2}\\}$ where
$\varepsilon$ is nullary, $\sigma_{1}$ is unary and $\sigma_{2}$ is binary.
The weight function $\mu$ is defined such that for all $n\in\mathbb{N}$:

$\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)=\setcounter{MaxMatrixCols}{14}\begin{bmatrix}y_{n,1}&\overline{y}_{n,1}&\ldots&\overline{y}_{n,k}&\overline{z}_{n,1}&\ldots&\overline{z}_{n,k}&\overline{w}_{n,1}&\ldots&\overline{w}_{n,k}&\overline{t}_{n,1}&\ldots&\overline{t}_{n,s}&1\end{bmatrix}$

To show how we build such weight function, let us write
$\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)$. Thus, we obtain from Equation 4
that for all $n\geq 1$,

$\boldsymbol{a}_{n}=\boldsymbol{a}_{n-1}\,\mu(\sigma_{1})(n,n-1)+\sum_{\ell=0}^{n-1}(\boldsymbol{a}_{\ell}\otimes\boldsymbol{a}_{n-1-\ell})\,\mu(\sigma_{2})(n,\ell,n-1-\ell)\,.$

The matrices $\mu(\sigma_{1})$ and $\mu(\sigma_{2})$ are defined as follows:

  * •

By definition, $\overline{y}_{n-1,1}=y_{n,1}$. Thus, we can set
$\mu(\sigma_{1})_{2,1}=1$ and $\mu(\sigma_{1})_{i,1}=0$ for all $i\neq 2$.
Moreover we also set $\mu(\sigma_{2})_{(i,j),1}=0$ for all
$i,j\in\\{1,\ldots,d\\}$.

  * •

Consider $j\in\\{2,\ldots,d-1\\}$. We know that $(\boldsymbol{a}_{n})_{j}$ is
of the form:

$A(n)+\sum_{h\in\Gamma}B_{h}(n,n-1)\overline{h}_{n-1}+\sum_{h,g\in\Gamma}\sum_{\ell=0}^{n-1}C_{h,g}(n,\ell,n-1-\ell)\,\overline{h}_{\ell}\,\overline{g}_{n-1-\ell}$

with $\Gamma=\\{w_{i},y_{i},z_{i}\\}_{i=1}^{k}\cup\\{t_{1},\ldots,t_{s}\\}$,
$A\in\mathbb{Q}_{u}(x_{0})$, $B_{h}\in\mathbb{Q}_{u}(x_{0},x_{1})$ and
$C_{h,g}\in\mathbb{Q}_{u}(x_{0},x_{1},x_{2})$. We now define:

    * –

$\mu(\sigma_{1})_{0,j}:=0$

    * –

$\mu(\sigma_{1})_{d,j}(x_{0},x_{1}):=A(x_{0})$

    * –

for all $h\in\Sigma$, if $i$ is the index corresponding to $h$ then
$\mu(\sigma_{1})_{i,j}(x_{0},x_{1}):=B_{h}(x_{0},x_{1})$.

    * –

for all $h,g\in\Gamma$, if $i_{1}$ and $i_{2}$ are respectively the indices
corresponding to $h$ and $g$ then
$\mu(\sigma_{2})_{(i_{1},i_{2}),j}(x_{0},x_{1},x_{2}):=C_{h,g}(x_{0},x_{1},x_{2})$

    * –

$\mu(\sigma_{2})_{(i_{1},i_{2}),j}=0$ when either $i_{1}=1$ or $i_{1}=d$ or
$i_{2}=1$ of $i_{2}=d$.

  * •

Finally, $\mu(\sigma_{1})_{d,d}:=1$ and $\mu(\sigma_{1})_{i,d}=0$ for $i\neq
d$.

Provided that

$\mu(\varepsilon)=\setcounter{MaxMatrixCols}{14}\begin{bmatrix}y_{0,1}&\overline{y}_{0,1}&\ldots&\overline{y}_{0,k}&\overline{z}_{0,1}&\ldots&\overline{z}_{0,k}&\overline{w}_{0,1}&\ldots&\overline{w}_{0,k}&\overline{t}_{0,1}&\ldots&\overline{t}_{0,s}&1\end{bmatrix}$

an easy proof by induction on $n$ (unfolding the definition of
$\mu(\sigma_{1})$ and $\mu(\sigma_{2})$) allows us to show that for all
$n\in\mathbb{N}$,

$\boldsymbol{a}_{n}=\setcounter{MaxMatrixCols}{14}\begin{bmatrix}y_{n,1}&\overline{y}_{n,1}&\ldots&\overline{y}_{n,k}&\overline{z}_{n,1}&\ldots&\overline{z}_{n,k}&\overline{w}_{n,1}&\ldots&\overline{w}_{n,k}&\overline{t}_{n,1}&\ldots&\overline{t}_{n,s}&1\end{bmatrix}$

We can therefore conclude that $f_{\mathcal{A}}(x)=y_{1}(x)$. ∎

######  Example 5.

Consider the solution $y_{1}(x)$ of the differential equation
$(y_{1}^{\prime})^{3}+y_{1}^{3}=1$ such that $y_{1}(0)=0$ and
$y^{\prime}_{1}(0)=1$. This equation cannot be put directly into a rational
dynamical system. However, by deriving the equation (following Proposition 5),
we deduce that $y_{1}(x)$ also satisfies
$3(y^{\prime}_{1})^{2}y^{\prime\prime}_{1}+3(y_{1})^{2}y^{\prime}_{1}=0$ which
leads to the following system:

$\left\\{\begin{array}[]{l}y^{\prime}_{1}=y_{2}\\\
y^{\prime}_{2}=-\frac{y^{2}_{1}}{y_{2}}\end{array}\right.$

Notice that as $y_{2}(0)=y^{\prime}_{1}(0)\neq 0$, we know from Theorem 6 that
there exists an automaton ${\mathcal{A}}$ such that
$f_{\mathcal{A}}(x)=y_{1}(x)$. To build this automaton, we follow the
construction in the proof of Theorem 6. Introducing only the non-trivial
variables, we obtain :

$\left\\{\begin{array}[]{l@{\quad}l}\Theta y_{1}=x\,y_{2}&y_{2}\Theta
y_{2}=x\,w_{2}\\\ &w_{2}=-y_{1}^{2}\end{array}\right.$

In term of relations between coefficients, we thus obtain:

$\overline{y}_{n,1}=\frac{1}{n+1}\overline{y}_{n-1,2}\qquad\overline{y}_{n,2}=\frac{1}{n+1}\left(\overline{w}_{n-1,2}-\sum_{\ell=0}^{n-1}\overline{y}_{\ell,2}(n-\ell)\overline{y}_{n-1-\ell,2}\right)$

Moreover, we have

$\overline{w}_{n,2}=-2y_{0,1}\overline{y}_{n,1}-\sum_{\ell=0}^{n-1}\overline{y}_{\ell,1}\overline{y}_{n-1-\ell,1}=-\sum_{\ell=0}^{n-1}\overline{y}_{\ell,1}\overline{y}_{n-1-\ell,1}$

Since none of the coefficient has a constant term, we build an automaton
${\mathcal{A}}$ such that
$\boldsymbol{a}_{n}=\begin{bmatrix}y_{n,1}&\overline{y}_{n,1}&\overline{y}_{n,2}&\overline{w}_{n,2}\end{bmatrix}$.
Therefore, we take

$\mu(\varepsilon)=\begin{bmatrix}0&1&0&0\end{bmatrix}\qquad\mu(\sigma_{1})(x_{0},x_{1})=\begin{bmatrix}0&0&0&0\\\
1&0&0&0\\\ 0&\frac{1}{x_{0}+1}&0&0\\\ 0&0&\frac{1}{x_{0}+1}&0\end{bmatrix}$

and

$\mu(\sigma_{2})(x_{0},x_{1},x_{2})=\begin{bmatrix}\boldsymbol{0}_{6\times
1}&\boldsymbol{0}_{6\times 1}&\boldsymbol{0}_{6\times
1}&\boldsymbol{0}_{6\times 1}\\\ 0&0&0&-1\\\ \boldsymbol{0}_{3\times
1}&\boldsymbol{0}_{3\times 1}&\boldsymbol{0}_{3\times
1}&\boldsymbol{0}_{3\times 1}\\\ 0&0&-\frac{x_{2}+1}{x_{0}+1}&0\\\
\boldsymbol{0}_{5\times 1}&\boldsymbol{0}_{5\times 1}&\boldsymbol{0}_{5\times
1}&\boldsymbol{0}_{5\times 1}\end{bmatrix}$

Running the automaton leads to the power series:

$y_{1}(x)=x-\frac{2}{4!}x^{4}-\frac{20}{7!}x^{7}-\frac{3320}{10!}x^{10}-\frac{1598960}{13!}x^{13}-\frac{1757280800}{16!}x^{16}-\ldots$

###  4.1 Application to counting combinatorial structures

Combinatorial species are a formalism for defining classes of combinatorial
structures [FZC94]. A species $A$ is a mapping (technically, a functor) that
takes a finite set of labels $U$ and returns a set, denoted $A[U]$, of
combinatorial structures labelled by $U$. For example, if $B$ is the species
of plane rooted binary trees then $B[\\{1,4,5\\}]$ is the set of trees shown
below:

$1$$4$$5$$1$$5$$4$$4$$5$$1$$5$$4$$1$$5$$1$$4$$4$$1$$5$

Note that all nodes do not have to be labelled. If $C$ is the species of plane
rooted binary trees with labels only on external nodes then $C[\\{1,2\\}]$
contains only two trees:

$1$$2$$2$$1$

To define species [FZC94] relies on a collection of constructions:  (i) The
initial object $\boldsymbol{1}$, which represents the empty structure without
label.  (ii) The variable $X$, which represents a single labelled node.  (iii)
The addition $A+B$, which represents the disjoints union of structures from
$A$ and $B$.  (iv) The product $A\cdot B$, which represents all the pairs of
elements from $A$ and $B$ over the input set of labels.  (v) The sequence
$\mathsf{sequence}(A)$, which generates the sequences of elements of $A$.
(vi) The set $\mathsf{set}(A)$, which generates the sets of elements of $A$.
(vii) The cycle $\mathsf{cycle}(A)$, which generates the cycles of elements of
$A$.

The constructions $\mathsf{set}$, $\mathsf{sequence}$ and $\mathsf{cycle}$
also allow constraints on the cardinality. For example,
$\mathsf{set}(A,card\geq 3)$ represents the sets of at least 3 elements of
$A$. A specification of species is then a (set of) equations that use these
constructions. In this setting, [FZC94] are interested in computing the
exponential generating series of a species $A$, corresponding to the power
series $\sum_{n=0}^{\infty}\frac{\|A[\\{1,\ldots,n\\}]\|}{n!}x^{n}$. In other
words, the $n$-th coefficient of the power corresponds to the numbers of
combinatorial structures in the species $A$ labelled by $\\{1,\ldots,n\\}$.

[3pt]—c—c—c—l——c—c—c—c—c—c—c—c—c—c—c—c— System & RDS Initial values Objects

$\left\\{\begin{array}[1]{l}y_{a}=x\,z\\\
z^{\prime}=z\,y_{a}^{\prime}\end{array}\right.$
$\left\\{\begin{array}[1]{l}y_{a}^{\prime}=z+\frac{x\,z^{2}}{1-x\,z}\\\
z^{\prime}=\frac{z^{2}}{1-x\,z}\end{array}\right.$ — Non plane trees

$y_{b}=x+y_{b}^{2}$ $y_{b}^{\prime}=\frac{1}{1-2\,y_{b}}$ $y_{b}(0)=0$ Plane
binary trees with external labels

$y_{c}=\frac{x}{1-y_{c}}$
$y_{c}^{\prime}=\frac{(1-y_{c})^{3}}{(1-y_{c})^{2}-x}$ $y_{c}(0)=0$ Plane
general trees

$\left\\{\begin{array}[]{l}y^{\prime}_{d}=y_{d}\,z^{\prime}\\\
z^{\prime}=\frac{1}{1-x}\end{array}\right.$ $y_{d}^{\prime}=\frac{y_{d}}{1-x}$
— Permutations

$\left\\{\begin{array}[]{l}y^{\prime}_{e}=y_{e}\,z_{2}^{\prime}\\\
z_{2}^{\prime}=\frac{y^{\prime}_{a}}{1-y_{a}}\\\ y_{a}=x\,z\\\
z^{\prime}=z\,y_{a}^{\prime}\end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{e}=y_{e}\,\frac{z}{1-y_{a}}+\frac{x\,z^{2}}{(1-x\,z)(1-y_{a})}\\\
y_{A}^{\prime}=z+\frac{x\,z^{2}}{1-x\,z}\\\
z^{\prime}=\frac{z^{2}}{1-x\,z}\end{array}\right.$ $y_{a}(0)=0$ Functional
graph

$\left\\{\begin{array}[]{l}y^{\prime}_{f}=y_{f}\,z\\\
z^{\prime}=z\end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{f}=y_{f}\,z\\\
z^{\prime}=z\end{array}\right.$ —  Set partitions (Bell Number)

$\left\\{\begin{array}[]{l}y_{g}=x+x\,z_{2}\\\
z_{2}^{\prime}=z_{1}\,y^{\prime}_{g}\\\
z_{1}^{\prime}=y_{g}\,y^{\prime}_{g}\end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{g}=\frac{1+z_{2}}{1-x\,z_{1}}\\\
z^{\prime}_{2}=\frac{y_{1}(1+z_{2})}{1-x\,z_{1}}\\\
z_{1}^{\prime}=y_{g}\frac{1+z_{2}}{1-x\,z_{1}}\\\ \end{array}\right.$ —  Non
plane ternary trees

$\left\\{\begin{array}[]{l}y_{h}=x+z_{2}\\\
z_{2}^{\prime}=z_{1}\,y^{\prime}_{h}\\\
z_{1}^{\prime}=z_{0}\,y^{\prime}_{h}\\\
z_{0}^{\prime}=z_{0}\,y^{\prime}_{h}\end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{h}=1+\frac{z_{1}}{1-z_{1}}\\\
z_{2}^{\prime}=\frac{z_{1}}{1-z_{1}}\\\
z^{\prime}_{1}=z_{0}+\frac{z_{0}\,z_{1}}{1-z_{1}}\\\
z_{0}^{\prime}=z_{0}+\frac{z_{0}\,z_{1}}{1-z_{1}}\\\ \end{array}\right.$
$\begin{array}[]{l}y_{h}(0)=0\\\ z_{1}(0)=0\\\ \end{array}$ Hierarchies

$\left\\{\begin{array}[]{l}y^{\prime}_{k}=y_{k}\,z^{\prime}_{1}\\\
z_{1}^{\prime}=\frac{z^{\prime}_{2}}{1-z_{2}}\\\ z_{2}=x\,z_{3}\\\
z_{3}^{\prime}=y_{g}\,y^{\prime}_{g}\\\ y_{g}=x+x\,z_{4}\\\
z_{4}^{\prime}=z_{5}\,y^{\prime}_{g}\\\
z_{5}^{\prime}=y_{g}\,y^{\prime}_{g}\end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{k}=y_{k}\frac{z_{3}}{1-x\,z_{3}}+y_{k}\frac{x\,y_{g}(1+z_{4})}{(1-x\,z_{5})(1-x\,z_{3})}\\\
z^{\prime}_{1}=\frac{z_{3}}{1-x\,z_{3}}+\frac{x\,y_{g}(1+z_{4})}{(1-x\,z_{5})(1-x\,z_{3})}\\\
z^{\prime}_{2}=z_{3}+x\,\frac{y_{g}(1+z_{4})}{1-x\,z_{5}}\\\
z^{\prime}_{3}=\frac{y_{g}(1+z_{4})}{1-x\,z_{5}}\\\
y^{\prime}_{g}=\frac{1+z_{4}}{1-x\,z_{5}}\\\
z^{\prime}_{4}=\frac{z_{5}(1+z_{4})}{1-x\,z_{5}}\\\
z_{5}^{\prime}=y_{g}\frac{1+z_{4}}{1-x\,z_{5}}\\\ \end{array}\right.$ —
3-constrained functional graphs

$\left\\{\begin{array}[]{l}y^{\prime}_{\ell}=y_{\ell}\,z_{1}\,z^{\prime}_{2}\\\
z^{\prime}_{1}=z_{1}\,z^{\prime}_{2}\\\ z_{2}^{\prime}=z_{3}\\\
z_{3}^{\prime}=y_{3}\\\ \end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{\ell}=y_{\ell}\,z_{1}\,z_{3}\\\
z^{\prime}_{1}=z_{1}\,z_{3}\\\ z_{3}^{\prime}=z_{3}\\\ \end{array}\right.$ —
3-balanced hierarchies

$\left\\{\begin{array}[]{l}y_{m}=\frac{1}{1-z_{1}}\\\ z_{1}^{\prime}=z_{0}\\\
z_{0}^{\prime}=z_{0}\\\ \end{array}\right.$
$\left\\{\begin{array}[]{l}y^{\prime}_{m}=\frac{z_{0}}{(1-z_{1})^{2}}\\\
z_{1}^{\prime}=z_{0}\\\ z_{0}^{\prime}=z_{0}\\\ \end{array}\right.$
$y_{m}(0)=1$ Surjections

Figure 3: Example of Species with RDA exponential generating series.
Unspecified initial values indicate that all power series solutions are
Rationally Dynamically Algebraic, no matter the initial values.

For instance, [FZC94] provides the following examples of specifications:

Specifications | Objects
---|---
$A=X\cdot\mathsf{set}(A)$ | Non-plane trees
$B=X+B\cdot B$ | Plane binary trees with only external labels
$C=X\cdot\mathsf{sequence}(C)$ | Plane general trees
$D=\mathsf{set}(\mathsf{cycle}(X))$ | Permutations
$E=\mathsf{set}(\mathsf{cycle}(A))$ | Functional graph
$F=\mathsf{set}(\mathsf{set}(X,card\geq 1))$ | Set partitions
$G=X+X\cdot\mathsf{set}(G,card=3)$ | Non-plane ternary trees
$H=X+\mathsf{set}(H,card\geq 2)$ | Hierarchies
$K=\mathsf{set}(\mathsf{cycle}(X\cdot\mathsf{set}(G,card=2)))$ | 3-constrained functional graphs
$L=\mathsf{set}(\mathsf{set}(\mathsf{set}(X,card\geq 1),card\geq 1))$ | 3-balanced hierarchies
$M=\mathsf{sequence}(\mathsf{set}(X,card\geq 1))$ | Surjections

These specifications represents standard objects in the literature. Here, non-
plane trees are trees in which the children of a node are unordered, whereas
in plane trees siblings are ordered. Functional graphs are directed graphs
with every node having outdegree 1 and 3-functional graphs are function graphs
where each node has indegree being 0 or 3.

Fortunately, [FZC94] also provides a way to translate every construct of the
specification into a system of differential equations on the associated
exponential generating functions. For instance, (i) $B=\mathsf{set}(A)$ is
translated to the equation $y_{B}^{\prime}=y_{B}\cdot y_{A}^{\prime}$;
(ii)Z$B=\mathsf{sequence}(A)$ is translated into $y_{B}=\frac{1}{1-y_{A}}$;
(iii) $B=\mathsf{cycle}(A)$ is translated into
$y_{B}^{\prime}=\frac{y_{A}^{\prime}}{1-y_{A}}$. We refer the reader to
[FZC94, Thereom 2] for a more detailed description of this translation.

We show in Figure 3 that each of the specifications presented above translates
into a system of differential equations and in addition we show that their
exponential generating series are all RDA power series.

Once the system of differential equations is transformed into a rational
dynamical system, checking that the exponential generating series is RDA only
requires checking that the rational functions are defined on the initial
values. In some cases, all initial values yield RDA power series: for example
for the systems of non-plane trees, permutations, 3-balanced hierarchies. In
the other cases, only specific initial values yield RDA power series (e.g.
Functional graphs). Thus so we present in Figure 3 the admissible initial
value of the exponential generating series of the species.

We highlight the cases of the Hierarchies and Surjections. For Hierarchies,
the initial value $y_{h}(0)=0$ is given by the specification. However,
understanding the initial value of $z_{1}(x)$ is less evident. For this, we
rely on the expression satisfied by $y_{h}(x)$ given in [FZC94]:
$y_{h}(x)=x+e^{y_{h}(x)}-1-y_{h}(x)$. From this we have
$y^{\prime}_{h}(x)=\frac{1}{2-e^{y_{h}(x)}}$ and
$z^{\prime}_{2}(x)=y^{\prime}_{h}(x)-1$. Since $y_{h}(0)=0$, we deduce that
$y^{\prime}_{h}(0)=1$ and $z^{\prime}_{2}(0)=0$. Hence,
$z_{2}^{\prime}(x)=z_{1}(x)y^{\prime}_{h}(x)$ yields $y_{1}(0)=0$.

For Surjections, the initial value $y_{m}(0)=1$ is given by the specification.
Therefore, as $(1-z_{1}(x))y_{m}(x)=1$, we deduce that $(1-z_{1}(0))\neq 0$.

##  5 Future Work

We have given algorithms for determining equivalence of holonomic tree
automata and their generating functions. For both holonomic recurrences and
weighted tree automata there are canonical notions of minimality and
associated minimisation algorithms [PZ13, KMW17]. Minimisation of recurrences
prove useful in practical applications [Kau23, Chapter 2.3] in which one wants
execute and manipulate automata and recurrences. However, when minimal
realisations are unique up to isomorphism, the problem of minimisation
transcends equality testing—two automata are equivalent if their minimal forms
are isomorphic. In future work we plan to investigate whether holonomic tree
automata admit canonical minimal realisations and, if so, to apply this to
obtaining optimal recurrences for combinatorial classes.

Our exposition has emphasised the generating functions of holonomic tree
automata over their formal tree series. It remains to explore the link between
such formal tree series and combinatorial objects. Such a relationship was
hinted at in Examples 1 and 2, and it is well understood that for families of
combinatorial objects with rational generating functions there is typically a
natural bijection between the objects and the words of a regular language.
Likewise for families of combinatorial objects with algebraic generating
functions, there is often a bijection between the objects and trees of of a
regular tree language (or the words of an unambiguous context-free language);
see [BM08, FS09] for a comprehensive exposition of this phenomenon.

### Acknowledgement

We would like to thank Gleb Pogudin for pointing out the paper [DL84]. Mahsa
Shirmohammadi and Ait El Manssour are supported by International Emerging
Actions grant (IEA’22) and by ANR grant VeSyAM (ANR-22- CE48-0005). James
Worrell was supported by UKRI Frontier Research Grant EP/X033813/1.

## References

  * [BCKN20] Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud.  Weakly-unambiguous parikh automata and their link to holonomic series.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP, volume 168 of LIPIcs, pages 114:1–114:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [BCN+23] Nikhil Balaji, Lorenzo Clemente, Klara Nosan, Mahsa Shirmohammadi, and James Worrell.  Multiplicity problems on algebraic series and context-free grammars.  In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023, pages 1–12. IEEE, 2023.
  * [BLL98] François Bergeron, Gilbert Labelle, and Pierre Leroux.  Combinatorial species and tree-like structures.  Number 67. Cambridge University Press, 1998.
  * [BM08] Mireille Bousquet-Mélou.  Rational and algebraic series in combinatorial enumeration.  arXiv preprint arXiv:0805.0588, 2008.
  * [BR82] Jean Berstel and Christophe Reutenauer.  Recognizable formal power series on trees.  Theor. Comput. Sci., 18:115–148, 1982.
  * [BR90] F. Bergeron and Christophe Reutenauer.  Combinatorial resolution of systems of differential equations iii: a special class of differentially algebraic series.  Eur. J. Comb., 11:501–512, 1990.
  * [BR10] Jean Berstel and Christophe Reutenauer.  Noncommutative rational series with applications.  2010\.
  * [CM17] Giusi Castiglione and Paolo Massazza.  On a class of languages with holonomic generating functions.  Theoretical Computer Science, 658:74–84, 2017.
  * [DKV09] Manfred Droste, Werner Kuich, and Heiko Vogler.  Handbook of weighted automata.  Springer Science & Business Media, 2009.
  * [DL84] Jan Denef and Leonard Lipshitz.  Power series solutions of algebraic differential equations.  Mathematische annalen, pages 213–238, 1984.
  * [DPV05] Manfred Droste, Christian Pech, and Heiko Vogler.  A kleene theorem for weighted tree automata.  Theory Comput. Syst., 38(1):1–38, 2005.
  * [FOR92] On rational state space realizations.  IFAC Proceedings Volumes, 25(13):341–346, 1992.  2nd IFAC Symposium on Nonlinear Control Systems Design 1992, Bordeaux, France, 24-26 June.
  * [FS09] Philippe Flajolet and Robert Sedgewick.  Analytic combinatorics.  cambridge University press, 2009.
  * [FZC94] Philippe Flajolet, Paul Zimmermann, and Bernard Van Cutsem.  A calculus for the random generation of labelled combinatorial structures.  Theor. Comput. Sci., 132(2):1–35, 1994.
  * [Kau23] Manuel Kauers.  D-finite Functions.  Springer, 2023.
  * [KMW17] Stefan Kiefer, Ines Marusic, and James Worrell.  Minimisation of multiplicity tree automata.  Log. Methods Comput. Sci., 13(1), 2017.
  * [Lan52] Serge Lang.  Hilbert’s nullstellensatz in infinite-dimensional space.  Proceedings of the American Mathematical Society, pages 407–410, 1952.
  * [LV86] Pierre Leroux and Gérard Viennot.  Combinatorial resolution of systems of differential equations, i. ordinary differential equations.  1986\.
  * [MW15] Ines Marusic and James Worrell.  Complexity of equivalence and learning for multiplicity tree automata.  J. Mach. Learn. Res., 16:2465–2500, 2015.
  * [NS09] Jana Nemcová and Jan Schuppen.  Realization theory for rational systems: The existence of rational realizations.  SIAM J. Control and Optimization, 48:2840–2856, 01 2009.
  * [OPV22] Alexey Ovchinnikov, Gleb Pogudin, and Thieu N Vo.  Bounds for elimination of unknowns in systems of differential-algebraic equations.  International Mathematics Research Notices, pages 12342–12377, 2022.
  * [PZ13] Marko Petkovšek and Helena Zakrajšek.  Solving linear recurrence equations with polynomial coefficients.  In Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, pages 259–284. Springer, 2013.
  * [Reu12] Christophe Reutenauer.  On a matrix representation for polynomially recursive sequences.  The Electronic Journal of Combinatorics [electronic only], 19, 09 2012.
  * [Sei90] Helmut Seidl.  Deciding equivalence of finite tree automata.  SIAM J. Comput., 19(3):424–437, 1990.
  * [SMK15] Helmut Seidl, Sebastian Maneth, and Gregor Kemper.  Equivalence of deterministic top-down tree-to-string transducers is decidable.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 943–962. IEEE Computer Society, 2015.
  * [Sta80] Richard P. Stanley.  Differentiably finite power series.  Eur. J. Comb., 1(2):175–188, 1980.
  * [vDH19] Joris van Der Hoeven.  Computing with d-algebraic power series.  Applicable Algebra in Engineering, Communication and Computing, pages 17–49, 2019.

##  Appendix A Algebraic operations on holonomic tree automata

This appendix is dedicated to the proof of the following theorem.

######  Theorem 7 (Closure properties).

The class of formal tree series recognisable by holonomic tree automata is
closed under addition, scalar product (in $\mathbb{Q}$) and product.

The class of generating functions of holonomic tree automata is closed under
addition, scalar product (in $\mathbb{Q}$), product, derivative, integral,
inverse, forward shift and backward shift.

For the class of formal tree series recognisable by holonomic tree automata,
the closure properties are given by the following propositions:

  * •

addition: Proposition 9

  * •

scalar product: Proposition 10

  * •

product: Proposition 11

For the class of generating functions of holonomic tree automata, the closure
properties are given by the following propositions:

  * •

addition and scalar product: Corollary 2

  * •

product: Corollary 4

  * •

derivation and integral: Corollary 3

  * •

inverse: Proposition 18

  * •

backward shift: Proposition 16

  * •

forward shift: Proposition 17

###  A.1 The class of formal tree series recognisable by holonomic tree
automata

######  Proposition 8.

Let ${\mathcal{A}}=(d,\mu)$ be a holonomic tree automaton over $\Sigma$. Let
$\boldsymbol{\beta}(x)\in\mathbb{Q}(x)^{d\times 1}$ defined on all non-
negative integers. There exists an automaton ${\mathcal{A}}^{\prime}$ over
$\Sigma$ such that for all $t\in T_{\Sigma}$,
${\mathcal{A}}^{\prime}[\\![t]\\!]=\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)$.

###### Proof.

We build the holonomic tree automaton by incrementing the dimension of
${\mathcal{A}}$ by 1 and by building the weight function $\mu^{\prime}$ such
that for all $t\in T_{\Sigma}$,
$\widetilde{\mu}^{\prime}(t)=\begin{bmatrix}\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)&\widetilde{\mu}(t)\end{bmatrix}$.
Formally, for all $a\in\Sigma_{0}$, we define
$\mu^{\prime}(a)=\begin{bmatrix}\mu(a)\beta(0)&\mu(a)\end{bmatrix}$; and for
all $g\in\Sigma_{k}$ with $k>0$,
$\mu^{\prime}(g)\in\mathbb{Q}[x_{0},\ldots,x_{k}]^{(d+1)^{k}\times(d+1)}$ and,
denoting
$M(x_{0},\ldots,x_{n})=\mu(g)(x_{0},\ldots,x_{n})\boldsymbol{\beta}(x_{0})$,
we have:

  * •

for all $j\in\\{2,\ldots,d+1\\}$, for all
$i_{1},\ldots,i_{k}\in\\{1,\ldots,d+1\\}$,

$\mu^{\prime}(g)_{(i_{1},\ldots,i_{k}),j}=\left\\{\begin{array}[]{lr}\mu(g)_{(i_{1}-1,\ldots,i_{k}-1),j-1}&\text{if
}\forall\ell.i_{\ell}\in\\{2,\ldots,d+1\\}\\\ 0&\text{otherwise
}\end{array}\right.$

  * •

for all $i_{1},\ldots,i_{k}\in\\{2,\ldots,d+1\\}$,

$\mu^{\prime}(g)_{(i_{1},\ldots,i_{k}),1}=\left\\{\begin{array}[]{lr}M_{(i_{1}-1,\ldots,i_{k}-1),1}&\text{if
}\forall\ell.i_{\ell}\in\\{2,\ldots,d+1\\}\\\
0&\text{otherwise}\end{array}\right.$

Take ${\mathcal{A}}^{\prime}=(d^{\prime},\mu^{\prime})$ with $d^{\prime}=d+1$,
we prove by induction on the structure of trees that for all $t\in
T_{\Sigma}$,
$\widetilde{\mu}^{\prime}(t)=\begin{bmatrix}\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)&\widetilde{\mu}(t)\end{bmatrix}$.
In the base case, $t$ is a leaf $a$ with $a\in\Sigma_{0}$, meaning that
$\widetilde{\mu}^{\prime}(a)=\mu^{\prime}(a)=\begin{bmatrix}\mu(a)\beta(0)&\mu(a)\end{bmatrix}=\begin{bmatrix}\widetilde{\mu}(a)\beta(0)&\widetilde{\mu}(a)\end{bmatrix}$.

In the inductive step, $t=g(t_{1},\ldots,t_{k})$ for some $g\in\Sigma_{k}$ and
$t_{1},\ldots,t_{k}\in T_{\Sigma}$. Let us denote $t_{0}=t$. Applying our
inductive hypothesis on $t_{1},\ldots,t_{k}$, we have for all
$i\in\\{1,\ldots,k\\}$,
$\widetilde{\mu}^{\prime}(t_{i})=\begin{bmatrix}\widetilde{\mu}(t_{i})\boldsymbol{\beta}(\|t_{i}\|)&\widetilde{\mu}(t_{i})\end{bmatrix}$.
Hence,

$\widetilde{\mu}^{\prime}(g(t_{1},\ldots,t_{k}))=(\begin{bmatrix}\widetilde{\mu}(t_{1})\boldsymbol{\beta}(\|t_{1}\|)&\widetilde{\mu}(t_{1})\end{bmatrix}\otimes\ldots\otimes\begin{bmatrix}\widetilde{\mu}(t_{k})\boldsymbol{\beta}(\|t_{k}\|)&\widetilde{\mu}(t_{k})\end{bmatrix})\mu^{\prime}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)$

By construction, for all $j\in\\{1,\ldots,d+1\\}$, for all
$(i_{1},\ldots,i_{k})\in\\{1,\ldots,d+1\\}^{k}$, if $i_{\ell}=1$ for some
$\ell$ then $\mu^{\prime}(g)_{(i_{1},\ldots,i_{k}),j}(x_{0},\ldots,x_{k})=0$.
Thus, for all $j\in\\{2,\ldots,d+1\\}$,

$\displaystyle\widetilde{\mu}^{\prime}(g(t_{1},\ldots,t_{k}))_{j}$
$\displaystyle=\sum_{(i_{1},\ldots,i_{k})\in\\{2,\ldots,d+1\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}^{\prime}(t_{\ell})_{i_{\ell}}\right)\mu^{\prime}(g)_{(i_{1},\ldots,i_{k}),j}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{(i_{1},\ldots,i_{k})\in\\{2,\ldots,d+1\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}-1}\right)\mu(g)_{(i_{1}-1,\ldots,i_{k}-1),j-1}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{(i_{1},\ldots,i_{k})\in\\{1,\ldots,d\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}}\right)\mu(g)_{(i_{1},\ldots,i_{k}),j-1}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\left((\widetilde{\mu}(t_{1})\otimes\ldots\otimes\widetilde{\mu}(t_{k}))\mu(g)(\|t_{0}\|,\ldots,\|t_{k}\|)\right)_{j-1}$
$\displaystyle=\widetilde{\mu}(g(t_{1},\ldots,t_{k}))_{j-1}$

Similarly, we also have:

$\displaystyle\widetilde{\mu}^{\prime}(g(t_{1},\ldots,t_{k}))_{1}$
$\displaystyle=\sum_{(i_{1},\ldots,i_{k})\in\\{2,\ldots,d+1\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}-1}\right)M_{(i_{1}-1,\ldots,i_{k}-1),1}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{(i_{1},\ldots,i_{k})\in\\{1,\ldots,d\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}}\right)M_{(i_{1},\ldots,i_{k}),1}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=(\widetilde{\mu}(t_{1})\otimes\ldots\otimes\widetilde{\mu}(t_{k}))\mu(g)(\|t_{0}\|,\ldots,\|t_{k}\|)\boldsymbol{\beta}(\|t_{0}\|)$
$\displaystyle=\widetilde{\mu}^{\prime}(g(t_{1},\ldots,t_{k}))\boldsymbol{\beta}(\|g(t_{1},\ldots,t_{k})\|)$

This concludes the proof of
$\widetilde{\mu}^{\prime}(t)=\begin{bmatrix}\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)&\widetilde{\mu}(t)\end{bmatrix}$
for all $t\in T_{\Sigma}$. As
${\mathcal{A}}^{\prime}[\\![t]\\!]=\widetilde{\mu}^{\prime}(t)_{1}$, we
conclude that
${\mathcal{A}}^{\prime}[\\![t]\\!]=\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)={\mathcal{A}}[\\![t]\\!]$
for all $t\in T_{\Sigma}$. ∎

######  Proposition 9.

Let ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ be two holonomic tree automata
over $\Sigma$. There exists a holonomic tree automaton ${\mathcal{A}}$ over
$\Sigma$ such that for all $t\in T_{\Sigma}$,
${\mathcal{A}}[\\![t]\\!]={\mathcal{A}}_{1}[\\![t]\\!]+{\mathcal{A}}_{2}[\\![t]\\!]$.

###### Proof.

Assume that ${\mathcal{A}}_{1}=(d_{1},\mu_{1})$ and
${\mathcal{A}}_{2}=(d_{2},\mu_{2})$. We build the automaton
${\mathcal{A}}^{\prime}=(d,\mu)$ of dimension $d=d_{1}+d_{2}$ such that

$\text{for all }t\in
T_{\Sigma},\widetilde{\mu}(t)=\begin{bmatrix}\widetilde{\mu}_{1}(t)&\widetilde{\mu}_{2}(t)\end{bmatrix}$

and we will then conclude by applying Proposition 8 with the automaton
${\mathcal{A}}^{\prime}$ and the vector $\boldsymbol{\beta}(x)$ defined as
follows to obtain the desired automaton ${\mathcal{A}}$.

$\boldsymbol{\beta}(x)=\begin{bmatrix}1\\\ \boldsymbol{0}_{(d_{1}-1)\times
1}\\\ 1\\\ \boldsymbol{0}_{(d_{2}-1)\times 1}\\\ \end{bmatrix}$

The definition of $\widetilde{\mu}$ is fairly straightforward: For all
$a\in\Sigma_{0}$, $\mu(a)=\begin{bmatrix}\mu_{1}(a)&\mu_{2}(a)\end{bmatrix}$.
Moreover, for all $g\in\Sigma_{k}$ with $k>0$, the matrix $\mu(g)$ is in
$\mathbb{Q}[x_{0},\ldots,x_{k}]^{d^{k}\times d}$ such that for all
$i_{1},\ldots,i_{k}\in\\{1,\ldots,d\\}$,

  * •

for all $j\in\\{1,\ldots,d_{1}\\}$,

$\mu(g)_{(i_{1},\ldots,i_{k}),j}=\left\\{\begin{array}[]{lr}\mu_{1}(g)_{(i_{1},\ldots,i_{k}),j}&\text{if
}\forall\ell.i_{\ell}\in\\{1,\ldots,d_{1}\\}\\\
0&\text{otherwise}\end{array}\right.$

  * •

for all $j\in\\{d_{1}+1,\ldots d\\}$,

$\mu(g)_{(i_{1},\ldots,i_{k}),j}=\left\\{\begin{array}[]{lr}\mu_{2}(g)_{(i_{1}-d_{1},\ldots,i_{k}-d_{1}),j-d_{1}}&\text{if
}\forall\ell.i_{\ell}\in\\{d_{1}+1,\ldots d\\}\\\
0&\text{otherwise}\end{array}\right.$

The proof of
$\widetilde{\mu}(t)=\begin{bmatrix}\widetilde{\mu}_{1}(t)&\widetilde{\mu}_{2}(t)\end{bmatrix}$
for all $t\in T_{\Sigma}$ is done by induction on the structure of the tree
$t$ and follows by construction of $\mu$. The base case, that is $t=a$ with
$a\in\Sigma_{0}$, is trivial by construction of $\mu(a)$. In the inductive
step, $t=g(t_{1},\ldots,t_{k})$ for some $g\in\Sigma_{k}$ and
$t_{1},\ldots,t_{k}\in T_{\Sigma}$. Let us denote $t_{0}=t$. By construction,
for all $j\in\\{1,\ldots,d_{1}\\}$, for all
$i_{1},\ldots,i_{k}\in\\{1,\ldots,d\\}$, $\mu(g)_{(i_{1},\ldots,i_{k}),j}=0$
when there exists $\ell$ such that $i_{\ell}\not\in\\{1,\ldots,d_{1}\\}$.
Thus, by applying our inductive hypothesis on $t_{1},\ldots,t_{k}$, we obtain
that for all $j\in\\{1,\ldots,d_{1}\\}$,

$\displaystyle\widetilde{\mu}(t)_{j}$
$\displaystyle=\sum_{i_{1},\ldots,i_{k}\in\\{1,\ldots,d\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}}\right)\mu(g)_{(i_{1},\ldots,i_{k}),j}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}}\right)\mu(g)_{(i_{1},\ldots,i_{k}),j}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{1}(t_{\ell})_{i_{\ell}}\right)\mu_{1}(g)_{(i_{1},\ldots,i_{k}),j}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\widetilde{\mu}_{1}(t)_{j}$

Similarly, we have by construction that for all $j\in\\{d_{1}+1,\ldots,d\\}$,
for all $i_{1},\ldots,i_{k}\in\\{1,\ldots,d\\}$,
$\mu(g)_{(i_{1},\ldots,i_{k}),j}=0$ when there exists $\ell$ such that
$i_{\ell}\not\in\\{d_{1}+1,\ldots,d\\}$. Hence, by applying our inductive
hypothesis on $t_{1},\ldots,t_{k}$, we obtain that for all
$j\in\\{d_{1}+1,\ldots,d\\}$,

$\displaystyle\widetilde{\mu}(t)_{j}$
$\displaystyle=\sum_{i_{1},\ldots,i_{k}\in\\{1,\ldots,d\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{i_{\ell}}\right)\mu(g)_{(i_{1},\ldots,i_{k}),j}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{i_{1},\ldots,i_{k}\in\\{d_{1}+1,\ldots,d\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{2}(t_{\ell})_{i_{\ell}-d_{1}}\right)\mu_{2}(g)_{(i_{1}-d_{1},\ldots,i_{k}-d_{1}),j-d_{1}}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\sum_{i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{2}\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{2}(t_{\ell})_{i_{\ell}}\right)\mu_{2}(g)_{(i_{1},\ldots,i_{k}),j-n}(\|t_{0}\|,\ldots,\|t_{k}\|)$
$\displaystyle=\widetilde{\mu}_{2}(t)_{j-d_{1}}\qed$

######  Proposition 10.

Let ${\mathcal{A}}$ be a holonomic tree automaton over $\Sigma$. Let
$\alpha\in\mathbb{Q}$. There exists a holonomic tree automaton
${\mathcal{A}}^{\prime}$ over $\Sigma$ such that for all $t\in T_{\Sigma}$,
${\mathcal{A}}^{\prime}[\\![t]\\!]=\alpha{\mathcal{A}}[\\![t]\\!]$.

###### Proof.

It suffices to apply Proposition 8 on ${\mathcal{A}}$ with the vector
$\boldsymbol{\beta}(x)=\alpha\,\boldsymbol{e}_{1}$, where $\boldsymbol{e}_{1}$
is the canonical vector. ∎

######  Proposition 11.

Let ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ be two holonomic tree automata
over $\Sigma$. There exists a holonomic tree automaton ${\mathcal{A}}$ over
$\Sigma$ such that for all $t\in T_{\Sigma}$,
${\mathcal{A}}[\\![t]\\!]={\mathcal{A}}_{1}[\\![t]\\!]\cdot{\mathcal{A}}_{2}[\\![t]\\!]$.

###### Proof.

We take ${\mathcal{A}}_{1}=(d_{1},\mu_{1})$ and
${\mathcal{A}}_{2}=(d_{2},\mu_{2})$. We build the automaton
${\mathcal{A}}=(d,\mu)$ of dimension $d=d_{1}d_{2}$ such that for all $t\in
T_{\Sigma}$,

$\widetilde{\mu}(t)=\begin{bmatrix}\widetilde{\mu}_{1}(t)_{1}\widetilde{\mu}_{2}(t)_{1}&\ldots&\widetilde{\mu}_{1}(t)_{1}\widetilde{\mu}_{2}(t)_{d_{2}}&\widetilde{\mu}_{1}(t)_{2}\widetilde{\mu}_{2}(t)_{1}&\ldots&\widetilde{\mu}_{1}(t)_{d_{1}}\widetilde{\mu}_{2}(t)_{d_{2}}\end{bmatrix}$

For that purpose, we construct the function $\mu$ as follows. For all
$a\in\Sigma_{0}$, for all $i\in\\{1,\ldots,d_{1}\\}$, for all
$j\in\\{1,\ldots,d_{2}\\}$, $\mu(a)_{(i,j)}=\mu_{1}(a)_{i}\mu_{2}(a)_{j}$. For
all $g\in\Sigma_{k}$ with $k>0$, for all
$i,i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}$, for all
$j,j_{1},\ldots,j_{k}\in\\{1,\ldots,d_{2}\\}$,

$\mu(g)_{((i_{1},j_{1}),\ldots,(i_{k},j_{k})),(i,j)}=\mu_{1}(g)_{(i_{1},\ldots,i_{k}),i}\cdot\mu_{2}(g)_{(j_{1},\ldots,j_{k}),j}$

By definition,
$\widetilde{\mu}(g(t_{1},\ldots,t_{k}))=(\widetilde{\mu}(t_{1})\otimes\ldots\otimes\widetilde{\mu}(t_{k}))\mu(g)(\|t_{0}\|,\ldots,\|t_{k}\|)$.
Therefore, denoting $t_{0}=t$ and applying our inductive hypothesis on each
$t_{1},\ldots,t_{k}$, we obtain that for all $i\in\\{1,\ldots,d_{1}\\}$, for
all $j\in\\{1,\ldots,d_{2}\\}$,

$\displaystyle\widetilde{\mu}$
$\displaystyle(t)_{(i,j)}=\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}\\\
j_{1},\ldots,j_{k}\in\\{1,\ldots,d_{2}\\}\end{subarray}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}(t_{\ell})_{(i_{\ell},j_{\ell})}\right)\cdot\mu(g)(\|t_{0}\|,\ldots,\|t_{k}\|)_{((i_{1},j_{1}),\ldots,(i_{k},j_{k})),(i,j)}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}\\\
j_{1},\ldots,j_{k}\in\\{1,\ldots,d_{2}\\}\end{subarray}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{1}(t_{\ell})_{i_{\ell}}\widetilde{\mu}_{2}(t_{\ell})_{j_{\ell}}\right)\cdot\mu_{1}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)_{(i_{1},\ldots,i_{k}),i}\cdot\mu_{2}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)_{(j_{1},\ldots,j_{k}),j}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}\\\
j_{1},\ldots,j_{k}\in\\{1,\ldots,d_{2}\\}\end{subarray}}\left(\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{1}(t_{\ell})_{i_{\ell}}\right)\mu_{1}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)_{(i_{1},\ldots,i_{k}),i}\right)\cdot$
$\displaystyle\qquad\left(\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{2}(t_{\ell})_{j_{\ell}}\right)\mu_{2}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)_{(j_{1},\ldots,j_{k}),j}\right)$
$\displaystyle=\left(\sum_{i_{1},\ldots,i_{k}\in\\{1,\ldots,d_{1}\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{1}(t_{\ell})_{i_{\ell}}\right)\mu_{1}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)_{(i_{1},\ldots,i_{k}),i}\right)\cdot$
$\displaystyle\qquad\left(\sum_{j_{1},\ldots,j_{k}\in\\{1,\ldots,d_{2}\\}}\left(\prod_{\ell=1}^{k}\widetilde{\mu}_{2}(t_{\ell})_{j_{\ell}}\right)\mu_{2}(g)(\|t_{1}\|,\ldots,\|t_{k}\|)_{(j_{1},\ldots,j_{k}),j}\right)$
$\displaystyle=\left((\widetilde{\mu}_{1}(t_{1})\otimes\ldots\otimes\widetilde{\mu}_{1}(t_{k}))\mu_{1}(g)(\|t_{1}\|,\ldots,\|t_{k}\|)\right)_{i}\cdot\left((\widetilde{\mu}_{2}(t_{1})\otimes\ldots\otimes\widetilde{\mu}_{2}(t_{k}))\mu_{2}(g)(\|t_{0}\|,\ldots,\|t_{k}\|)\right)_{j}$
$\displaystyle=\widetilde{\mu}_{1}(t)_{i}\cdot\widetilde{\mu}_{2}(t)_{j}$

We conclude by noticing that
${\mathcal{A}}[\\![t]\\!]=\widetilde{\mu}(t)_{1}=\widetilde{\mu}_{1}(t)_{1}\widetilde{\mu}_{2}(t)_{1}={\mathcal{A}}_{1}[\\![t]\\!]\cdot{\mathcal{A}}_{2}[\\![t]\\!]$.
∎

###  A.2 Operations on the generating functions

We start by showing that when considering generating functions, we can always
restrict ourselves to alphabets $\Sigma$ where two different function symbols
must have different arity. In other words, there can only be one nullary
function symbol, one unary function symbol, one binary function symbol, etc.
We say in this case that $\Sigma$ is _arity distinct_.

######  Proposition 12.

Let ${\mathcal{A}}$ be a holonomic tree automaton over $\Sigma$. There exists
a holonomic tree automaton ${\mathcal{A}}^{\prime}$ over arity distinct
$\Sigma^{\prime}$ such that
$f_{{\mathcal{A}}}(x)=f_{{\mathcal{A}}^{\prime}}(x)$.

###### Proof.

Let ${\mathcal{A}}=(d,\mu)$. Let $r$ be the largest arity in $\Sigma$. For all
$k\in\\{0,\ldots,r\\}$, we define a new function symbol $h_{k}$ of arity $k$
and we build $\Sigma^{\prime}=\\{h_{k}\\}_{k=0}^{r}$. Additionally, we build
the automaton ${\mathcal{A}}^{\prime}=(d,\mu^{\prime})$ such that for all
$k\in\\{0,\ldots,r\\}$, $\mu^{\prime}(h_{k})=\sum_{g\in\Sigma_{k}}\mu(g)$.

Consider now the vector of power series
$\boldsymbol{f}(x)=\sum_{n=0}^{\infty}\boldsymbol{a}_{n}x^{n}$ where
$\boldsymbol{a}_{n}=\sum_{\begin{subarray}{c}t\in T_{\Sigma}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}(t)$. Similarly, consider the vector of
power series $\boldsymbol{g}(x)=\sum_{n=0}^{\infty}\boldsymbol{b}_{n}x^{n}$
where $\boldsymbol{b}_{n}=\sum_{\begin{subarray}{c}t\in T_{\Sigma^{\prime}}\\\
\|t\|=n\end{subarray}}\widetilde{\mu}^{\prime}(t)$. We show by induction on
$n$ that for all $n\in\mathbb{N}$, $\boldsymbol{a}_{n}=\boldsymbol{b}_{n}$.

In the base case ($n=0$),
$\boldsymbol{a}_{0}=\sum_{a\in\Sigma_{0}}\widetilde{\mu}(a)=\sum_{a/0\in\Sigma}\mu(a)=\mu^{\prime}(h_{0})=\widetilde{\mu}^{\prime}(h_{0})=\boldsymbol{b}_{0}$.
In the inductive step ($n>0$), from Equation 4, we deduce that

$\displaystyle\boldsymbol{a}_{n}$
$\displaystyle=\sum_{k=1}^{r}\;\sum_{g\in\Sigma_{k}}\;\sum_{\begin{subarray}{c}n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\mu(g)(n,n_{1},\ldots,n_{k})$
$\displaystyle=\sum_{k=1}^{r}\sum_{\begin{subarray}{c}n,n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\sum_{g\in\Sigma_{k}}\mu(g)(n,n_{1},\ldots,n_{k})$
$\displaystyle=\sum_{k=1}^{r}\sum_{\begin{subarray}{c}n,n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}(\boldsymbol{a}_{n_{1}}\otimes\ldots\otimes\boldsymbol{a}_{n_{k}})\mu^{\prime}(h_{k})(n,n_{1},\ldots,n_{k})$
$\displaystyle=\sum_{k=1}^{r}\sum_{\begin{subarray}{c}n,n_{1},\ldots,n_{k}\in\mathbb{N}\\\
n_{1}+\ldots+n_{k}=n-1\end{subarray}}(\boldsymbol{b}_{n_{1}}\otimes\ldots\otimes\boldsymbol{b}_{n_{k}})\mu^{\prime}(h_{k})(n,n_{1},\ldots,n_{k})\qquad\text{by
inductive hypothesis}$ $\displaystyle=\boldsymbol{b}_{n}$

As $f_{\mathcal{A}}(x)=\boldsymbol{f}(x)_{1}$ and
$f_{{\mathcal{A}}^{\prime}}(x)=\boldsymbol{g}(x)_{1}$, we conclude. ∎

######  Proposition 13.

Let ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ be two holonomic tree automata
over $\Sigma_{1}$ and $\Sigma_{2}$ respectively. Therefore exist an alphabet
$\Sigma$ and two holonomic tree automata ${\mathcal{A}}^{\prime}_{1}$ and
${\mathcal{A}}^{\prime}_{2}$ over $\Sigma$ such that
$f_{{\mathcal{A}}_{1}}(x)=f_{{\mathcal{A}}^{\prime}_{1}}(x)$ and
$f_{{\mathcal{A}}_{2}}(x)=f_{{\mathcal{A}}^{\prime}_{2}}(x)$.

###### Proof.

Take ${\mathcal{A}}_{1}=(d_{1},\mu_{1})$ and
${\mathcal{A}}_{2}=(d_{2},\mu_{2})$. By Proposition 12, we can also assume
that $\Sigma_{1}$ and $\Sigma_{2}$ are arity distinct.

Let $r_{1}$ and $r_{2}$ the maximum arity of symbols in $\Sigma_{1}$ and
$\Sigma_{2}$. Let $\\{k_{1},\ldots,k_{\ell}\\}$ be the set of arity in
$\\{0,\ldots,r_{2}\\}$ such that for all $i\in\\{1,\ldots,\ell\\}$,
$\Sigma_{2}$ contains a symbol of arity $k_{i}$ but not $\Sigma_{1}$. We
define $\Sigma^{\prime}_{1}$ by extending $\Sigma_{1}$ with the fresh symbols
$h_{k_{1}},\ldots,h_{k_{\ell}}$ of arity $k_{1},\ldots,k_{\ell}$ respectively
and we extend ${\mathcal{A}}_{1}$ into
${\mathcal{A}}^{\prime}_{1}=(d_{1},\mu^{\prime}_{1})$ such that
$\mu^{\prime}_{1}(h_{k_{i}})=\boldsymbol{0}_{d_{1}^{k_{i}}\times d_{1}}$ for
all $i\in\\{1,\ldots,\ell\\}$. We trivially have
$f_{{\mathcal{A}}_{1}}(x)=f_{{\mathcal{A}}^{\prime}_{1}}(x)$.

We extend in a similar fashion $\Sigma_{2}$ and ${\mathcal{A}}_{2}$ by
computing $\\{k^{\prime}_{1},\ldots,k^{\prime}_{\ell^{\prime}}\\}$ to be the
set of arities in $\\{0,\ldots,r_{1}\\}$ such that for all
$i\in\\{1,\ldots,\ell^{\prime}\\}$, $\Sigma_{1}$ contains a symbol of arity
$k^{\prime}_{i}$ but not $\Sigma_{2}$. This yields an automaton
${\mathcal{A}}^{\prime}_{2}$ over $\Sigma^{\prime}_{2}$ such that
$f_{{\mathcal{A}}^{\prime}_{2}}(x)=f_{{\mathcal{A}}_{2}}(x)$. As $\Sigma_{1}$
and $\Sigma_{2}$ are arity distinct, we have by construction that
$\Sigma^{\prime}_{1}$ is a renaming of $\Sigma^{\prime}_{2}$. Therefore, we
can fully rename the automaton ${\mathcal{A}}^{\prime}_{1}$ to be over
$\Sigma^{\prime}_{2}$ with
$f_{{\mathcal{A}}_{1}}(x)=f_{{\mathcal{A}}^{\prime}_{1}}(x)$. ∎

######  Corollary 2.

Let ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ be two holonomic tree
automata. Let $\alpha\in\mathbb{Q}$.

  * •

there exists a holonomic tree automaton such that
$f_{{\mathcal{A}}}(x)=f_{{\mathcal{A}}_{1}}(x)+f_{{\mathcal{A}}_{2}}(x)$.

  * •

there exists a holonomic tree automaton such that $f_{{\mathcal{A}}}(x)=\alpha
f_{{\mathcal{A}}_{1}}(x)$.

###### Proof.

Direct from Propositions 13, 9 and 10. ∎

######  Proposition 14.

Let ${\mathcal{A}}$ be a holonomic tree automaton. There exists a holonomic
tree automaton ${\mathcal{A}}^{\prime}$ such that
$f_{{\mathcal{A}}^{\prime}}(x)=\Theta
f_{{\mathcal{A}}}(x)=xf^{\prime}_{\mathcal{A}}(x)$.

###### Proof.

Let ${\mathcal{A}}=(d,\mu)$ over the alphabet $\Sigma$. Let us consider the
vector $\boldsymbol{\beta}(x)=\begin{bmatrix}x\\\ \boldsymbol{0}_{(d-1)\times
1}\end{bmatrix}$. By Proposition 8, there exists a holonomic tree automaton
${\mathcal{A}}^{\prime}$ such that
${\mathcal{A}}^{\prime}[\\![t]\\!]=\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)=\|t\|\widetilde{\mu}(t)_{1}=\|t\|{\mathcal{A}}[\\![t]\\!]$
for all $t\in T_{\Sigma}$. Hence, we directly obtain that
$f_{{\mathcal{A}}^{\prime}}(x)=\sum_{n=0}n\sum_{\begin{subarray}{c}t\in
T_{\Sigma}\\\ \|t\|=n\end{subarray}}{\mathcal{A}}[\\![t]\\!]x^{n}$. By
Proposition 1, we conclude that $f_{{\mathcal{A}}^{\prime}}(x)=\Theta
f_{{\mathcal{A}}}(x)$. ∎

######  Proposition 15.

Let ${\mathcal{A}}$ be a holonomic tree automaton. There exists a holonomic
tree automaton ${\mathcal{A}}^{\prime}$ such that
$f_{{\mathcal{A}}^{\prime}}(x)=\frac{1}{x}\int_{0}^{x}f_{{\mathcal{A}}}(x)dx$.

###### Proof.

Let ${\mathcal{A}}=(d,\mu)$ over an alphabet $\Sigma$. Let us consider the
vectore $\boldsymbol{\beta}(x)=\begin{bmatrix}\frac{1}{1+x}\\\
\boldsymbol{0}_{(d-1)\times 1}\end{bmatrix}$. By Proposition 8, there exists a
holonomic tree automaton ${\mathcal{A}}^{\prime}$ such that
${\mathcal{A}}^{\prime}[\\![t]\\!]=\widetilde{\mu}(t)\boldsymbol{\beta}(\|t\|)=\frac{1}{1+\|t\|}\widetilde{\mu}(t)_{1}=\frac{1}{1+\|t\|}{\mathcal{A}}[\\![t]\\!]$.
Hence, we directly obtain that:

$f_{{\mathcal{A}}^{\prime}}(x)=\sum_{n=0}\frac{1}{1+n}\sum_{\begin{subarray}{c}t\in
T_{\Sigma}\\\
\|t\|=n\end{subarray}}{\mathcal{A}}[\\![t]\\!]x^{n}=\frac{1}{x}\int_{0}^{x}f_{{\mathcal{A}}}(x)dx\qed$

######  Proposition 16.

Let ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ be two holonomic tree
automata.

  * •

There exists a holonomic tree automaton ${\mathcal{A}}$ such that
$f_{{\mathcal{A}}}(x)=x\cdot f_{{\mathcal{A}}_{1}}(x)$.

  * •

There exists a holonomic tree automaton ${\mathcal{A}}$ such that
$f_{{\mathcal{A}}}(x)=x\cdot f_{{\mathcal{A}}_{1}}(x)\cdot
f_{{\mathcal{A}}_{2}}(x)$.

###### Proof.

Without loss of generality, let us assume that ${\mathcal{A}}_{1}$ and
${\mathcal{A}}_{2}$ are automata over distinct alphabet $\Sigma^{1}$ and
$\Sigma^{2}$ (we can always rename the function symbols otherwise). Let
${\mathcal{A}}_{1}=(d_{1},\mu_{1})$ and ${\mathcal{A}}_{2}=(d_{2},\mu_{2})$.

We start by building ${\mathcal{A}}$ such that $f_{{\mathcal{A}}}(x)=x\cdot
f_{{\mathcal{A}}_{1}}(x)$. Let us take a new unary symbol $u/1$ not already in
$\Sigma^{1}$. We build the automaton ${\mathcal{A}}$ to have dimension
$d_{1}+1$ over $\Sigma=\\{u\\}\cup\Sigma^{1}$ with the weight function $\mu$
such that for all $a\in\Sigma^{1}_{0}$,
$\mu(a)=\begin{bmatrix}0&\mu_{1}(a)\end{bmatrix}$; and for all $k>0$, for all
$g\in\Sigma^{1}_{k}$, for all $i_{1},\ldots,i_{k},j\in\\{1,\ldots,d_{1}+1\\}$,

$\mu(g)_{(i_{1},\ldots,i_{k}),j}=\left\\{\begin{array}[]{lr}\mu_{1}(g)_{(i_{1}-1,\ldots,i_{k}-1),j-1}&\text{if
}\forall\ell.i_{\ell},j\in\\{2,\ldots,d_{1}+1\\}\\\
0&\text{otherwise}\end{array}\right.$

and

$\mu(u)(x_{0},x_{1})=\begin{bmatrix}0&\boldsymbol{0}_{1\times d_{1}}\\\
1&\boldsymbol{0}_{1\times d_{1}}\\\ \boldsymbol{0}_{(d_{1}-1)\times
1}&\boldsymbol{0}_{(d_{1}-1)\times d_{1}}\\\ \end{bmatrix}$

With such a construction, we can show the following property: for all $t\in
T_{\Sigma}$,

  * •

if $t\in T_{\Sigma^{1}}$ then
$\widetilde{\mu}(t)=\begin{bmatrix}0&\widetilde{\mu}_{1}(t)\end{bmatrix}$;

  * •

if $t=u(t^{\prime})$ with $t^{\prime}\in T_{\Sigma^{1}}$ then