Alin Bostan
email: alin.bostan@inria.fr

Arnaud Carayol
email: arnaud.carayol@u-pem.fr

Florent Koechlin
email: florent.koechlin@u-pem.fr

Cyril Nicaud
email: cyril.nicaud@u-pem.fr

Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Keywords: 2012 ACM Subject Classification Theory of computation → Formal languages and automata theory; Mathematics generating series, holonomicity, ambiguity, reversal bounded counter machine, Parikh automata Automata, Logic, Semantics, and Theory of Programming

We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series. We first prove a strong version of a conjecture by Castiglione and Massazza: weakly-unambiguous Parikh automata are equivalent to unambiguous two-way reversal bounded counter machines, and their multivariate generating series are holonomic. We then show that the converse is not true: we construct a language whose generating series is algebraic (thus holonomic), but which is inherently weakly-ambiguous as a Parikh automata language. Finally, we prove an effective decidability result for the inclusion problem for weakly-unambiguous Parikh automata, and provide an upper-bound on its complexity.

Introduction

This article investigates the link between holonomic (or D-finite) power series and formal languages. We consider the classical setting in which this connection is established via the generating series L(x) = n≥0 n x n counting the number n of words of length n in a given language L. On the languages side, the Chomsky-Schützenberger hierarchy [START_REF] Chomsky | The Algebraic Theory of Context-Free Languages[END_REF] regroups languages in classes of increasing complexity: regular, context-free, context-sensitive and recursively enumerable. For power series, a similar hierarchy exists, consisting of the rational, algebraic and holonomic series. The first two levels of each hierarchy share a strong connection, as the generating series of a regular (resp. unambiguous context-free) language is a rational (resp. algebraic) power series.

This connection has borne fruits both in formal language theory and in combinatorics. In combinatorics, finite automata and unambiguous grammars are routinely used to establish rationality and algebraicity of particular power series. In formal languages, this connection was (implicitly) used to give polynomial-time algorithms for the inclusion and universality 114:2 Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series tests for unambiguous finite automata [START_REF] Stearns | On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata[END_REF]. In [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF], Flajolet uses the connection between unambiguous context-free grammars and algebraic series to prove the inherent ambiguity of certain context-free languages, solving several conjectures with this tool. Using analytic criteria on the series (for instance, the existence of infinitely many singularities), he establishes that the series of these context-free languages is not algebraic. Hence these languages cannot be described by unambiguous context-free grammars and are therefore inherently ambiguous.

In this article we propose to extend the connection to holonomic series. Holonomic series enjoy non-trivial closure properties whose algorithmic counterparts are actively studied in computer algebra. Our aim is to show that these advances can be leveraged to obtain nontrivial results in the formal languages and verification worlds. These results are particularly noteworthy as the notion of unambiguity in automata theory is not fully understood [START_REF] Colcombet | Unambiguity in automata theory[END_REF]. The work of extending the connection was already initiated by Massazza in [START_REF] Massazza | Holonomic functions and their relation to linearly constrained languages[END_REF], where he introduces two families of languages, named RCM1 and linearly constrained languages (LCL), whose generating series are holonomic. These classes are, however, not captured by well-known models of automata, and this limits their appeal. Recently, Castiglione and Massazza addressed this issue and conjectured that RCM contains the languages accepted by deterministic one-way reversal bounded machines (RBCM for short) [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF]; Massazza proved the result for RBCM for two subclasses of one-way deterministic RBCM [START_REF] Massazza | On the conjecture L dfcm RCM[END_REF][START_REF] Massazza | On the generating functions of languages accepted by deterministic onereversal counter machines[END_REF]. This conjecture hints that the class RCM is related to models of automata such as RBCM, which are used in program verification.

Our first contribution is to prove a stronger version of this conjecture. We show that RCM and LCL respectively correspond to the languages accepted by weakly-unambiguous2 version of Parikh automata (PA, for short) [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF] and pushdown Parikh automata. Intuitively, Parikh automata are3 finite non-deterministic word automata enriched with the ability to test semilinear constraints between the number of occurrences of each transition in the run. In terms of RBCM, these classes correspond to unambiguous two-way RBCM and unambiguous one-way RBCM enriched with a stack. Parikh automata are also commonly used in program verification. In view of the literature, these results might seem expected but they still require a careful adaptation of the standard techniques in the absence of a stack and become even more involved when a stack is added.

After having established the relevance of the classes of languages under study, we provide two consequences of the holonomicity of their associated generating series.

The first consequence follows Flajolet's approach mentioned previously and gives criteria to establish the inherent weak-ambiguity for languages accepted by PA or pushdown PA, by proving that their generating series are not holonomic. These criteria are sufficient but not necessary; this is not surprising as the inherent weak-ambiguity is undecidable for languages accepted by PA. Yet, the resulting method captures non-trivial examples with quite short and elegant proofs. In contrast, we give an example of inherently weakly-ambiguous PA language having a holonomic series (and therefore not amenable to the analytic method) for which we prove inherent weak-ambiguity by hand. The proof is quite involved but shows the inherent ambiguity of this language for a much larger class of automata (i.e., PA whose semi-linear sets are replaced by arbitrary recursive sets).

114:3

The second consequence is of an algorithmic nature. We focus on the inclusion problem for weakly-unambiguous PA, whose decidability can be deduced from Castiglione and Massazza's work [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF]. Here our contribution is an effective decidability result: we derive a concrete bound B, depending on the size of the representation of the two PAs, such that the inclusion holds if and only if the languages are included when considering words up to the length B. This bound B is obtained by a careful analysis of the proofs establishing the closure properties of holonomic series (in several variables), notably under Hadamard product and specialization. We do this by controlling various parameters (order, size of the polynomial coefficients, . . . ) of the resulting partial differential equations.

Primer on holonomic power series in several variables

In this section, we introduce power series in several variables and the classes of rational, algebraic and holonomic power series. We recall the connection with regular and context-free languages via the notions of generating series in one or several variables.

Let Q[x 1 , . . . , x k ] be the ring of polynomials in the variables x 1 , . . . , x k with coefficients in Q and let Q(x 1 , . . . , x k ) be the associated field of rational functions.

The generating series of a sequence (f n ) n∈N is the (formal) power series in the variable x defined by F (x) = n∈N f n x n . More generally, the generating series of a sequence a(n 1 , . . . , n k ) is a multivariate (formal) power series in the variables x 1 , . . . , x k defined by

A(x 1 , . . . , x k ) = (n1,...,n k )∈N k a(n 1 , . . . , n k )x n1 1 . . . x n k k .
In this article, we only consider power series whose coefficients belong to the field Q. The set of such k-variate power series is denoted Q

[[x 1 , . . . , x k ]].
Power series are naturally equipped with a sum and a product which generalize those of polynomials, for which Q[[x 1 , . . . , x k ]] is a ring. We use the bracket notation for the coefficient extraction:

[x n1 1 . . . x n k k ]A(x 1 , . . . , x k ) = a(n 1 , . . . , n k ). The sup- port of A ∈ Q[[x 1 , . . . , x k ]] is the set of (n 1 , . . . , n k ) such that [x n1 1 . . . x n k k ]A = 0. The inverse 1/A of a series A ∈ Q[[x 1 , . . . , x k ]] is well-defined when its constant term [x 0 1 . . . x 0 k ]A is not zero. For instance, the inverse of A(x 1 , x 2 ) = 1 -x 1 x 2 2 is 1 1-x1x 2 2 = n≥0 x n 1 x 2n 2 .
The generating series of a language L over the alphabet Σ = {a 1 , . . . , a k } is the univariate power series L(x) = w∈L x |w| = n∈N n x n , where n counts the number of words of length n in L. Similarly the multivariate generating series of L defined by L(x a1 , . . . , x a k ) = (n1,...,n k )∈N k (n 1 , . . . , n k )x n1 a1 . . . x n k a k where (n 1 , . . . , n k ) denotes the number of words w in L such that |w| a1 = n 1 , |w| a2 = n 2 , . . . , and |w| a k = n k , and |w| a denotes the number of occurrences of a ∈ Σ in w. This way, we create one dimension per letter, so that each letter a ∈ Σ has a corresponding variable x a .

Observe that the univariate generating series of a language is exactly L(x, . . . , x), obtained by setting each variable to x in its multivariate generating series.

Example 1. The generating series of the language P of well-nested parentheses defined by the grammar S → aSbS

+ ε is P (x a , x b ) = 1- √ 1-4xax b 2xax b
and its counting series is 4

P (x) = 1- √ 1-4x 2 2x 2
. Indeed the production of the grammar translates to the equation P (x a , x b ) = x a x b P (x a , x b ) 2 + 1. This equation admits only one power series solution, namely

1- √ 1-4xax b 2xax b
. 4 As for the inverse, the square root of a power series with nonzero constant term can be defined using the usual Taylor formula

√ 1 -x = n≥0 1 (1-2 n) 4 n 2 n n x n .
I C A L P 2 0 2 0 114:4 Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series A power series A(x 1 , . . . , x k ) = n1,...,n k a(n 1 , . . . , n k )x n1 1 . . . x n k k is rational if it satisfies an equation of the form: P (x 1 , . . . , x k )A(x 1 , . . . , x k ) = Q(x 1 , . . . , x k ), with P, Q ∈ Q[x 1 , . . . , x k ] and P = 0. The generating series (both univariate and multivariate) of regular languages (i.e., languages accepted by a finite state automaton) are rational power series [START_REF] Bousquet-Mélou | Rational and algebraic series in combinatorial enumeration[END_REF]. It is well-known that the generating series can be effectively computed from a deterministic automaton accepting the language (see for instance [17, §I.4.2] for a detailed proof). For example, the multivariate generating series of the regular language (abc) * is

1 1-xax b xc = n≥0 x n a x n b x n c .
Its univariate generating series is 1 1-x 3 . The connection between rational languages and rational power series is not tight. For instance, the generating series of the non-regular context-free language {a n b n : n ≥ 0} is 1 1-xax b , which is rational. In fact, it has the same generating series as the regular language (ab) * . Also there exist rational power series with coefficients in N which are not the generating series of any rational language. This is the case for

x+5x 2
1+x-5x 2 -125x 3 as shown in [START_REF] Bousquet-Mélou | Rational and algebraic series in combinatorial enumeration[END_REF]. A power series A(x 1 , . . . , x k ) is algebraic if there exists a non-zero polynomial P ∈ Q[x 1 , . . . , x k , Y ] such that P (x 1 , . . . , x k , A(x 1 , . . . , x k )) = 0. All rational series are algebraic.

Example 2. The series

1 1-x1x2 = n≥0 x n 1 x n 2 is rational, as it satisfies the equation (1 -x 1 x 2 )A(x 1 , x 2 ) = 1. The series A(x 1 , x 2 ) = √ 1 -x 1 x 2 is algebraic but not rational, since A(x 1 , x 2 ) 2 + (x 1 x 2 -1)
= 0 and there is no similar algebraic equation of degree 1.

The reader is referred to [START_REF] Stanley | Enumerative combinatorics[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF] for a detailed account on rational and algebraic series.

In the same manner that rational series satisfy linear equations and algebraic series satisfy polynomial equations, holonomic series satisfy linear differential equations with polynomial coefficients. To give a precise definition, we need to introduce the formal partial differentiation of power series. The differential operator ∂ xi with respect to the variable x i is defined by

∂ xi A(x 1 , . . . , x k ) = n1,...,n k n i a(n 1 , . . . , n k )x n1 1 . . . x ni-1 i-1 x ni -1 i x ni+1 i+1 . . . x n k k .
The composed operator ∂ j xi is inductively defined for j ≥ 1 by

∂ 1 xi = ∂ xi and ∂ j+1 xi = ∂ xi • ∂ j xi .
Definition 3 (see [START_REF] Stanley | Differentiably finite power series[END_REF][START_REF] Lipshitz | D-finite power series[END_REF]). A power series A(x 1 , . . . , x k ) is holonomic or D-finite 5 if the Q(x 1 , . . . , x k )-vector space spanned by the family

{∂ i1 x1 . . . ∂ i k x k A(x 1 , . . . , x k ) : (i 1 , . . . , i k ) ∈ N k } has a finite dimension. Equivalently, for every variable z ∈ {x 1 , . . . , x k }, A(x 1 , . . . , x k ) satisfies a linear differential equation of the form P r (x 1 , . . . , x k )∂ r z A(x 1 , . . . , x k ) + . . . + P 0 (x 1 , . . . , x k )A(x 1 , . . . , x k ) = 0, where the P i 's are polynomials of Q[x 1 , . . . , x k ] with P r = 0.
In the sequel, except for Section 5, we rely on the closure properties of the holonomic series and will not need to go back to Definition 3.

Example 4. A simple example of holonomic series is

A(x) = e x 2 = n≥0 x 2n n! . It is holonomic (in one variable) since it satisfies ∂ x A(x) -2xA(x) = 0.
For a more involved example, consider the language

L 3 = {w ∈ {a, b, c} * : |w| a = |w| b = |w| c },
containing the words having the same number of occurrences of a's, b's and c's. This language is classically not context-free. Moreover there are 3n n,n,n words of length 3n in L 3

5 A priori, these notions differ: a function A(x1, . . . , x k ) is called D-finite if all its partial derivatives ∂ n1 x1 • • • ∂ nk xk • A generate a finite dimensional space over Q(x1, . . . , x k ), and holonomic if the functions x α1 1 • • • x αk k ∂ β1 x1 • • • ∂ βk xk • A subject to the constraint α1 + • • • + α k + β1 + • • • + β k ≤ N span a vector space whose dimension over Q grows like O(N k ).
The equivalence of these notions is proved by deep results of Bernšteȋn [START_REF] Bernstein | Analytic continuation of generalized functions with respect to a parameter[END_REF] and Kashiwara [START_REF] Kashiwara | On the holonomic systems of linear differential equations[END_REF][START_REF] Takayama | An approach to the zero recognition problem by Buchberger algorithm[END_REF].

and the power series

n≥0 3n n,n,n x n is transcendental [15, §7]. Its multivariate generating series L 3 (x a , x b , x c ) is equal to n≥0 (3 n)! (xax b xc) n (n!) 3
and satisfies the partial differential equation: Holonomic series are an extension of the hierarchy we presented, as stated in the following proposition (see [START_REF] Comtet | Calcul pratique des coefficients de Taylor d'une fonction algébrique[END_REF] for a proof, and [START_REF] Bostan | Differential equations for algebraic functions[END_REF] for bounds, algorithms and historical remarks).

(27x 2 a x b x c -x a )∂ 2 xa f (x a , x b , x c ) + (54x a x b x c -1)∂ xa f (x a , x b , x c ) + 6x b x c f (x a , x b , x c ) = 0,

Proposition 5. Multivariate algebraic power series are holonomic.

In the univariate case6 , a power series A(x) = n a n x n is holonomic if and only if its coefficients satisfy a linear recurrence of the form p r (n)a n+r + . . . + p 0 (n)a n = 0, where every p i is a polynomial with rational coefficients [START_REF] Stanley | Differentiably finite power series[END_REF]Th. 1.2].

We now focus on these closure properties.

Proposition 6 ([33]

). Multivariate holonomic series are closed under sum and product.

Holonomic series are also closed under substitution by algebraic series as long as the resulting series is well-defined7 .

Proposition 7 [START_REF] Lipshitz | D-finite power series[END_REF]Prop. 2.3]). Let A(x 1 , . . . , x k ) be a power series and let G i (y 1 , . . . , y ) be algebraic power series such that B(y 1 , . . . , y ) = A(G 1 (y 1 , . . . , y ), . . . , G k (y 1 , . . . , y )) is well-defined as a power series. If A is holonomic, then B is also holonomic.

A sufficient condition for the substitution to be valid is that G i (0, . . . , 0) = 0 for all i (see [START_REF] Stanley | Differentiably finite power series[END_REF]Th. 2.7]). For the case

G 1 = • • • = G k = 1, called the specialization to 1, a sufficient condition is that for every index (i 1 , . . . , i k ), [x i1 1 . . . x i k k ]A is a polynomial in y 1 , .
. . , y . The Hadamard product is the coefficient-wise multiplication of power series. If the series A(x 1 , . . . , x k ) and B(x 1 , . . . , x k ) are the generating series of the sequences a(n 1 , . . . , n k ) and b(n 1 , . . . , n k ), the Hadamard product A B of A and B is the power series defined by

A B(x 1 , . . . , x k ) = (n1,...,n k )∈N k a(n 1 , . . . , n k )b(n 1 , . . . , n k )x n1 1 . . . x n k k .
Observe that the support of F G is the intersection of the supports of F and G.

Theorem 8 ([25]). Multivariate holonomic series are closed under Hadamard product.

Example 9. The generating series of the language L 3 of Example 4, which is not contextfree, can be expressed using the Hadamard product: since

L 3 (x a , x b , x c ) = 1 1-(xa+x b +xc) 1 1-xax b xc
, which is not algebraic. One of our main technical contributions is to provide bounds on the sizes of the polynomials in the differential equations of the holonomic representation of the Hadamard product of two rational series P1 Q1 and P2 Q2 : we prove that their maxdegree is at most (kM ) O(k) and that the logarithm of their largest coefficient is at most (kM ) O(k 2 ) (1 + log S ∞ ), where M (resp. S ∞ ) is the maxdegree plus one (resp. largest coefficient) in P 1 , Q 1 , P 2 and Q 2 .

Weakly-unambiguous Parikh automata

In this section, we introduce weakly-unambiguous Parikh automata and show that their multivariate generating series are holonomic. We establish that they accept the same languages as unambiguous two-way reversal bounded counter machines [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF]. Finally, we prove that the class of accepted languages coincides with Massazza's RCM class [START_REF] Massazza | Holonomic functions and their relation to linearly constrained languages[END_REF][START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF]. Parikh automata (PA for short) were introduced in [START_REF] Klaedtke | Parikh automata and Monadic Second-Order logics with linear cardinality constraints[END_REF][START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF]. Informally, a PA is a finite automaton whose transitions are labeled by pairs (a, v) where a is a letter of the input alphabet and v is a vector in N d . A run q 0 a1,v1

---→ q 1 a2,v2 ---→ q 2 • • • q n-1 an,vn ----→ q n computes the word a 1 • • • a n and the vector v 1 + • • • + v n
where the sum is done component-wise. The acceptance condition is given by a set of final states and a semilinear set of vectors. A run is accepting if it reaches a final state and if its vector belongs to the semilinear set.

0 1 2 a 1 0 0 a 1 0 0 a 1 0 0 , b 0 1 0 , c 0 0 1
The PA depicted above, equipped with the semilinear constraint {(n 1 , n 2 , n 1 + n 2 ) : n 1 , n 2 ≥ 0}, accepts the set of words w over {a, b, c} that start and end with a and that are such that |w| a + |w| b = |w| c .

Semilinear sets and their characteristic series

A set L ⊆ N d is linear if it is of the form c + P * := {c + λ 1 p 1 + • • • + λ k p k : λ 1 , . . . , λ k ∈ N},
where c ∈ N d is the constant of the set and P = {p 1 , . . . , p k } ⊂ N its set of periods. A set C ⊆ N d is semilinear if it is a finite union of linear sets. For example, the semilinear set {(n 1 , n 2 , n 1 + n 2 ) : n 1 , n 2 ≥ 0} is in fact a linear set (0, 0, 0) + {(1, 0, 1), (0, 1, 1)} * .

In [START_REF] Eilenberg | Rational sets in commutative monoids[END_REF][START_REF] Ito | Every semilinear set is a finite union of disjoint linear sets[END_REF], it is shown that every semilinear set admits an unambiguous presentation. A presentation c + P * with P = {p 1 , . . . , p k } of a linear set L is unambiguous if for all x ∈ L, the λ i 's such that x = c + λ 1 p 1 + • • • + λ k p k are unique. An unambiguous presentation of a semilinear set is given by a disjoint union of unambiguous linear sets. A bound on the size of the equivalent unambiguous presentation is given in [START_REF] Chistikov | The taming of the semi-linear set[END_REF].

Semilinear sets are ubiquitous in theoretical computer science and admit numerous characterizations. They are the rational subsets of the commutative monoid (N d , +), the unambiguous rational subset of (N d , +) [START_REF] Eilenberg | Rational sets in commutative monoids[END_REF][START_REF] Ito | Every semilinear set is a finite union of disjoint linear sets[END_REF], the Parikh images of context-free languages [START_REF] Rohit | On context-free languages[END_REF], the sets definable in Presburger arithmetic [START_REF] Presburger | Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt[END_REF], the sets defined by boolean combinations of linear inequalities, equalities and equalities modulo constants.

For example, the semilinear set {(2n, 3n, 5n) : n ≥ 0} is equal to (0, 0, 0) + {(2, 3, 5)} * . It is also the Parikh image of the regular (hence context-free) language (aabbbccccc) * . In (N, +), it is defined by the Presburger formula φ(x, y, z) = ∃w, x = w + w ∧ y = w + w + w ∧ z = w + w + w + w + w. Finally it is characterized in N 3 by the equalities 3x = 2y and 5x = 2z.

For a semilinear set C ⊆ N d , we consider its characteristic generating series

C(x 1 , . . . , x d ) defined by (i1,...,i d )∈C x i1 1 • • • x i d d .
It is well-known [START_REF] Eilenberg | Rational sets in commutative monoids[END_REF][START_REF] Ito | Every semilinear set is a finite union of disjoint linear sets[END_REF] that this power series is rational 8 .

8

The characteristic series of an unambiguous linear set c + P * ⊆ N with P = {p1, . . . ,

p k } is x c(1) 1 . . . x c(d) d k i=1 1 -x pi(1) 1 • • • x pi(d) d
-1 and hence is rational. As an unambiguous semilinear set is the disjoint union of unambiguous linear sets, its characteristic series is the sum of their series and it is therefore rational.

Weakly-unambiguous PAs and their generating series

We now introduce PA and their weakly-unambiguous variant. We discuss the relationship with the class of unambiguous PA introduced by Cadilhac et al. in [START_REF] Cadilhac | Unambiguous constrained automata[END_REF] and the closure properties of this class.

A Parikh automaton of dimension d ≥ 1 is a tuple A = (Σ, Q, q I , F, C, ∆) where Σ is the alphabet, Q is the set of states, q

I ∈ Q is the initial state, F ⊆ Q is the set of final states, C ⊆ N d is the semilinear constraint and ∆ ⊆ Q × (Σ × N d ) × Q is the transition relation.
A run of the automaton is a sequence q 0 a1,v1

---→ q 1 a2,v2 ---→ q 2 • • • q n-1 an,vn ----→ q n where for all i ∈ [1, n], (q i-1 , (a i , v i ), q i ) is a transition in ∆. The run is labeled by the pair (a 1 • • • a n , v 1 + • • • + v n ) ∈ Σ * × N d . It is accepting if q 0 = q I ,
the state q n is final and if the vector v 1 + • • • + v n belongs to C. The word w is then said to be accepted by A. The language accepted by A is denoted by L(A).

To define a notion of size for a PA, we assume that the constraint set is given by an unambiguous presentation p i=1 c i + P * i . We denote by |A| := |Q| + |∆| + p + i |P i | and by A ∞ the maximum coordinate of a vector appearing in ∆, the c i 's and the P i 's. Definition 10. A Parikh automaton is said to be weakly-unambiguous if for every word there is at most one accepting run.

A language is inherently weakly-ambiguous if it cannot be accepted by any weaklyunambiguous PA. The language S (defined in Section 4.1) is an example 9 of a language accepted by a non-deterministic PA which is inherently weakly-ambiguous.

Remark 11. We consider here the standard notion of unambiguity for finite state machines. However we decided to use the name weakly-unambiguous to avoid the confusion with the class of unambiguous PA which appears in the literature. This class was introduced by Cadilhac et al. in [START_REF] Cadilhac | Unambiguous constrained automata[END_REF] for constraint automata, a model equivalent to PA and was latter defined directly on PAs. This notion of unambiguity is more restrictive than ours: they call a Parikh automaton unambiguous if the underlying automaton on letters, where the vectors have been erased, is unambiguous. Clearly such automata are weakly-unambiguous. However the converse is not true. Consider the language L = {c n w :

w = x 1 x 2 • • • x m ∈ {a, b} * ∧ m ≥ n > 0 ∧ |x 1 x 2 • • • x n | a < |x 1 x 2 • • • x n | b }
over the alphabet {a, b, c}. Using results from [START_REF] Cadilhac | Unambiguous constrained automata[END_REF], one can show that it is not recognized by any unambiguous Parikh automata. However, it is accepted by the weakly-unambiguous automaton depicted in Fig. 1 below with the semilinear {(n 1 , n 2 , n 3 ) :

n 1 = n 2 + n 3 and n 2 < n 3 }.
The lack of expressivity of unambiguous PAs is counter-balanced by their closure under boolean operations, which is explained by their link with a class of deterministic PA [START_REF] Cadilhac | Unambiguous constrained automata[END_REF][START_REF] Filiot | Two-Way Parikh Automata[END_REF]. It was pointed out to us by a reviewer that the class of weakly-unambiguous PA is briefly considered, under the name OneCA, in Cadilhac's PhD thesis [5, p. 117], where only basic properties are established, in particular the strict inclusion of unambiguous PA in this class.

Using a standard product construction when the vectors are concatenated and using the concatenation of the constraints, it is easy to show that weakly-unambiguous PA are closed under intersection. In [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF], the authors claim that the class 10 is closed under union. However their construction has an irrecoverable flaw and we do not know if weakly-unambiguous PA are closed under union or under complementation. 9 Using the equivalences between weakly-unambiguous PA and RCM established in Proposition 13 and PA and RBCM [START_REF] Klaedtke | Parikh automata and Monadic Second-Order logics with linear cardinality constraints[END_REF][START_REF] Cadilhac | Affine Parikh automata[END_REF], it also gives an example of a language accepted by a RBCM with a non-holonomic generating series (strengthening Theorem 12 of [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF]) and a witness for the strict inclusion of RCM in RBCM announced in Theorem 11 of [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF]. Remark that their proof of this theorem only shows that there exists no recursive translation from RBCM to RCM. 10 Actually, their claim is for the class RCM, which we will show to be equivalent in Section 3.4.

= x1x2 • • • xm ∈ {a, b} * ∧ m ≥ n > 0 ∧ |x1x2 • • • xn|a < |x1x2 • • • xn| b } over the alphabet {a, b, c} with the semilinear constraint {(n1, n2, n3) : n1 = n2 + n3 and n2 < n3}.
We now give a very short proof of the fact that weakly-unambiguous languages in PA have holonomic generating series. The idea of the proof can be traced back to [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]. A similar proof was given in [START_REF] Massazza | Holonomic functions and their relation to linearly constrained languages[END_REF] for languages in the class RCM but using the closure under algebraic substitutions instead of specialization (see Remark 25).

Our approach puts into light a different multivariate power series associated with a weakly-unambiguous PA A of dimension d. The multivariate weighted generating series G(x, y 1 , . . . , y d ) of A is such that for all indices (n, i 1 , . . . , i d ), [x n y i1 1 . . . y i d d ]G counts the number of words of length n accepted by A with a run labeled by the vector (i 1 , . . . , i d ).

Proposition 12. The generating series of the language recognized by a weakly-unambiguous Parikh automaton is holonomic.

Proof. Let A be a weakly-unambiguous PA with a constraint set C ⊆ N d . We first prove that its weighted series G(x, y 1 , . . . , y d ) is holonomic. As holonomic series are closed under Hadamard product (see Theorem 8), it suffices to express G as the Hadamard product of two rational series A and C in the variables x, y 1 , . . . , y d .

The first series A(x, y 1 , . . . , y d ) is such that for all n, i 1 , . . . , i d ≥ 0, [x n y i1 1 . . . y i d d ]A counts the number of runs of A starting in q I , ending in a final state and labeled with a word of length n and the vector (i 1 , . . . , i d ). Note that we do not require that (i 1 , . . . , i d ) belongs to C. As this series simply counts the number of runs in an automaton, its rationality is proved via the standard translation of the automaton into a linear system of equations.

For the second series, we take C(x, y 1 , . . . , y d ) := 1 1-x C(y 1 , . . . , y d ) where C is the support series of C, which is rational (see [START_REF] Eilenberg | Rational sets in commutative monoids[END_REF][START_REF] Ito | Every semilinear set is a finite union of disjoint linear sets[END_REF]). A direct computation yields that for all n, i 1 , . . . , i d ≥ 0, [x n y i1 1 . . . y i d d ]C is equal to 1 if (i 1 , . . . , i d ) belongs to C and 0 otherwise. The Hadamard product of A and C counts the number of runs accepting a word of length n with the vector (i 1 , . . . , i d ). As A is weakly-unambiguous, this quantity is equal to the number of words of length n accepted with this vector. Hence G = Ā C.

The univariate series A(x) of A is equal to G(x, 1, . . . , 1). Indeed, for all n ≥ 0, ,y d ) is the sum over all vectors i ∈ N d of the number of words of length n accepted with the vector i. As A is weaklyunambiguous, each word is accepted with at most one vector and this sum is therefore equal to the total number of accepted words of length n. Thanks to Proposition 7, A(x) = G(x, 1, . . . , 1) is holonomic.

[x n ]G(x, 1, . . . , 1) = i=(i1,...,i d ) [x n y i1 1 . . . y i d d ]G(x, y 1 , . . .

Equivalence with unambiguous reversal bounded counter machines

A k-counter machine [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF] is informally a Turing machine with one read-only tape that contains the input word, and k counters. Reading a letter a on the input tape, in a state q, the machine can check which of its counters are zero, increment or decrement its counters, change its state, and move its read head one step to the left or right, or stay on its current position. Note that the machine does not have access to the exact value of its counters. A k-counter machine is said (m, n)-reversal bounded if its reading head can change direction between left and right at most m times, and if every counter can alternate between incrementing and decrementing at most n times each. Finally, a reversal bounded counter machine (RBCM) is a k-counter machine which is (m, n)-reversal bounded for some m and n. A RBCM is unambiguous if for every word there is at most one accepting computation.

RBCM are known 11 to recognize the same languages as Parikh automata (see [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF][START_REF] Klaedtke | Parikh automata and Monadic Second-Order logics with linear cardinality constraints[END_REF][START_REF] Cadilhac | Affine Parikh automata[END_REF]). This equality does not hold anymore for their deterministic versions [START_REF] Cadilhac | Affine Parikh automata[END_REF]Prop. 3.14]. However, the proof of the equivalence for the general case can be slightly modified to preserve unambiguity.

Proposition 13. The class of languages accepted by unambiguous RBCM and weaklyunambiguous PA coincide.

Proof sketch. Unambiguous RBCMs are shown to be equivalent to one-way unambiguous RBCMs. In turn these are shown to be equivalent to weakly-unambiguous PA with εtransitions, which in turn are equivalent to weakly-unambiguous PA. This ε-removal step needs to be adapted to preserve weak-unambiguity. A language L over Σ belongs to RCM if there exist a regular language R over Γ = {a 1 , . . . , a d }, a semilinear set 12 Proof sketch. Every language in RCM can be accepted by a weakly-unambiguous PA that guesses the underlying word over Γ: the weak-unambiguity is guaranteed by the injectivity of the morphism. Conversely a language accepted by a weakly-unambiguous PA is in RCM by taking for R the set of runs of the PA and translating the constraint: the injectivity of the morphism is guaranteed by the weak-unambiguity of the PA.

Equivalence with RCM

In [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF], the authors conjectured that the class RCM contains the one-way deterministic RBCM. From Theorem 14 and Proposition 13 we get a stronger result: Corollary 15. The languages in RCM are the languages accepted by unambiguous RBCM. 11 The proof in [START_REF] Klaedtke | Parikh automata and Monadic Second-Order logics with linear cardinality constraints[END_REF] contains a patchable error, that was corrected in [START_REF] Cadilhac | Affine Parikh automata[END_REF]. 12 Our definition may seem a little more general than Massazza's, which only uses semilinear defined without modulo constraints, but it can be shown that the classes are equivalent.

I C A L P 2 0 2 0 114:10 Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Weakly-unambiguous pushdown Parikh automata

A pushdown Parikh automaton (PA for short) is a PA where the finite automaton is replaced by a pushdown automaton. A weakly-unambiguous PA has at most one accepting run for each word. Most results obtained previously can be adapted for weakly-unambiguous PA. However, unsurprisingly, the class of languages accepted by weakly-unambiguous PA is not closed under union and intersection. This can be shown using the inherent weak-ambiguity of the language D proved in Section 4.1. The closure under complementation is left open.

Proposition 16. The generating series of a weakly-unambiguous PA is holonomic.

Proof. The proof is almost identical to the proof of Proposition 12. The only difference is that the series A is algebraic and not rational. Indeed it counts the number of runs in a pushdown automaton and the language of runs is a deterministic context-free language even if the pushdown automaton is not deterministic.

Remark that using the same techniques, we can prove that the generating series of weakly-unambiguous Parikh tree automata are holonomic. As we proved that all these series are also generating series of PAs, we do not elaborate on this model in this extended abstract.

RBCMs can be extended with a pushdown storage to obtain a RBCM with a stack [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF].

Theorem 17. Weakly-unambiguous PA are equivalent to unambiguous one-way RBCM with a stack. Proof sketch. We first establish that unambiguous one-way RBCM with a stack are equivalent to weakly-unambiguous PA with ε-transitions. Contrarily to the PA case, the removal of ε-transitions is quite involved and uses weighted context-free grammars.

The class LCL of [START_REF] Massazza | Holonomic functions and their relation to linearly constrained languages[END_REF] is defined 13 as RCM is, except that the regular language is replaced by an unambiguous context-free14 language. Similarly to the PA case, one can prove: Proposition 18. LCL is the set of languages accepted by weakly-unambiguous PA.

Examples of inherently weakly-ambiguous languages

There is a polynomial-time algorithm to decide whether a given PA is weakly-unambiguous. But inherent weak-unambiguity is undecidable, as a direct application of a general theorem from [START_REF] Greibach | A note on undecidable properties of formal languages[END_REF]. This emphasizes that inherent weak-ambiguity is a difficult problem in general.

Two examples using an analytic criterion

Following an idea from Flajolet [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF] for context-free languages, the link between weaklyunambiguous PA and holonomic series yields sufficient criteria to establish inherent weakambiguity, of analytic flavor: the contraposition of Proposition 12 indicates that if L is recognized by a PA but its generating series is not holonomic, then L is inherently weaklyambiguous. Hence, any criterion of non-holonomicity can be used to establish the inherent weak-ambiguity. Many such criteria can be obtained when considering the generating series as analytic functions (of complex variables). See [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF][START_REF] Flajolet | On the non-holonomic character of logarithms, powers, and the nth prime function[END_REF] for several examples. For the presentation of this method in this extended abstract, we only rely on the following property:

Proposition 19 ([33]). A holonomic function in one variable has finitely many singularities.

Our first example is the language D, defined over the alphabet {a, b} as follows:

D = {n 1 n 2 . . . n k : k > 0, n 1 = 1 and ∃j < k, n j+1 = 2n j }, where n = a n b.
This language is recognized by a weakly-ambiguous Parikh automaton, which guesses the correct j, and then verifies that n j+1 = 2n j . Let D = ab(a * b) * \ D, and suppose by contradiction that D can be recognized by a weakly-unambiguous PA. Then its generating series should be holonomic by Proposition 12. Since the generating series of

D is D(x a , x b ) = xax b 1- x b 1-xa -D(x a , x b
), it should be holonomic too. Looking closely at the form of the words of D, we get that its generating series is

k≥1 x 2 k -1 a x k b .
It is not holonomic as xD(x, 1) + x has infinitely many singularities, see [15, p. 296-297].

Our second example is Shamir's language S = {a n bv 1 a n v 2 : n ≥ 1, v 1 , v 2 ∈ {a, b} * }. One can easily design a PA recognizing S, where one coordinate stands for the length of the first run of a's and the other one for the second run of a's, the automaton guessing when the second run starts. Flajolet proved that S is inherently ambiguous as a context-free language, since its generating series S(z) = z(1-z)

1-2z n 1 z 2n
1-2z+z n+1 has an infinite number of singularities [15, p. 296-297]. This also yields its inherent weak-ambiguity as a PA language.

Limit of the method: an example using pumping techniques

As already mentioned, the analytic method presented is not always sufficient to prove inherent ambiguity. In this section, we develop an example where it does not apply. We consider the following language L even , which is accepted both by a deterministic pushdown automaton and a non-deterministic PA (where n = a n b as in Section 4.1):

L even = n 1 n 2 . . . n 2k : k ∈ N, ∀i ≤ 2k, n i > 0, and ∃j ≤ k, n 2j = n 2j-1 .
In other words, L even is the language of sequences of encoded numbers having two consecutive equal values, the first one being at an odd position. This language is accepted by a nondeterministic PA but is also deterministic context-free. This means that its generating series is algebraic and hence holonomic. This puts it out of the reach of our analytic method.

In this section we establish the following result:

Theorem 20. The language L even is inherently weakly-ambiguous as a PA language.

The remainder of this section is devoted to sketch the proof of this proposition. By contradiction, we suppose that L even is recognized by a weakly-unambiguous PA A.

An a-piece ω of A is a non-empty simple path of a-edges in A, starting and ending at the same state: the states of the path are pairwise distinct, except for its extremities. The origin of w is its starting (and ending) state. Let Π(A) be the (finite) set of a-pieces in A.

We see a run in A as a sequence of transitions forming a path in A. An a-subpath of a run R in A is a maximal consecutive subsequence of R whose transitions are all labeled by a's, that is, it cannot be extended further to the left nor to the right in R using a's.

Let R be an accepting run in A. One can show that every a-subpath S of R can be decomposed as

S = w 1 σ s1 1 w 2 σ s2 2 • • • w f σ s f f w f +1
, where the σ i 's are a-pieces of Π(A), the s i 's are positive integers, and the w i 's are paths not using twice the same state. Moreover, this decomposition is unique if we add the condition that if w i = ε, then σ i = σ i-1 and the only state in common in w i and σ i is the origin of σ i . This is done by repeatedly following the path until a state q is met twice, factorizing this segment of the form wσ, where σ is an a-piece of origin q. We call this decomposition the canonical form of S, and the signature of S is the tuple (w 1 , σ 1 , w 2 , . . . , w f , σ f , w f +1 ), i.e., we dropped the s i 's of the canonical form. From the weak-unambiguity of A we can prove that there are at most c distinct possible signatures, where c only depends on A, and that f is always at most |Q A |.

Ramsey's Theorem [32] guarantees that there exists an integer r such that any complete undirected graph with at least r vertices, whose edges are colored using c 2 different colors, admits a monochromatic triangle. We fix two positive integers n and k sufficiently large, which will be chosen later on, depending on A only. For ∈ {1, . . . , r}, let w be the word w = n 1 n 2 . . . n 2r , where n i = n for odd i and n 2i = n + k if i = and n 2 = n. Each w is in L even , with a match at position 2 only. By weak-unambiguity, each w has a unique accepting run R in A, each such run having 2r a-subpaths by construction. For i = j in {1, . . . , r}, let λ ij be the signature of the 2j-th a-subpath of R i , which is a path of length n + k by definition. The complete undirected graph of vertex set {1, . . . , r} where each edge ij, with i < j, is colored by the pair (λ ij , λ ji ) admits a monochromatic triangle of vertices α < β < γ. In particular, λ αβ = λ αγ and λ γα = λ γβ .

We choose k = lcm({|σ| : σ ∈ Π(A)}), and n sufficiently large so that any a-subpath of an accepting run contains an a-piece σ repeated at least k + 1 times. This is possible as the w i 's have bounded length, and there are at most |Q A | + 1 of them. Hence, the 2γ-th a-subpath of w α contains a a-piece σ that is repeated more than s times, where s = k/|σ|. As λ αβ = λ αγ , the piece σ is also in the 2β-th a-subpath of w α . If we alter the accepting path R α into R α by looping s more times in σ in the a-subpath at position 2β and s less times in σ at position 2γ, we obtain a run for the word w =

• • • n n 2α • • • n n + 2k 2β • • • n n 2γ • • • . This
run is accepting as the PA computes the same vector as for w α , by commutativity of vectors addition. And the signatures remain unchanged, as there are sufficiently many repetitions of σ at position 2γ in w α . Similarly, as λ γα = λ γβ , we can alter the accepting path R γ into an accepting path R γ of same signatures as R γ for the same word w, by removing s = k/|σ | iterations of an a-piece σ at position 2α and adding them at position 2β.

We have built two paths R α and R γ that both accept the same word w. Therefore, as A is weakly-unambiguous, they are equal. As the signatures have not changed, this implies that the signature at position 2α in R α is λ γα , which is equal to λ γβ (monochromaticity), which is equal to λ αβ (R α and R γ have same signatures). This is a contradiction as we could remove one a-piece at position 2α in w α and add it at position 2β, while computing the same vector with the same starting and ending states: but this word is not in L even .

Remark 21. The proof relies on manipulations of paths in the automaton, and we only use the commutativity of the addition for the vector part. Thus, it still holds if we consider automata where we use a recursively enumerable set instead of a semilinear set for acceptance.

Algorithmic consequence of holonomicity

Generating series of languages have already been used to obtain efficient algorithms on unambiguous models of automata. For instance, they were used by Stearns and Hunt as a basic tool to obtain bounds on the length of a word witnessing the non-inclusion between two unambiguous word automata [START_REF] Stearns | On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata[END_REF]. More precisely, the proof in [START_REF] Stearns | On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata[END_REF] relies on the recurrence equation satisfied by the coefficients of the generating series (which is guaranteed to exist by holonomicity in one variable). In the rational case, this recurrence relation can be derived from the automaton and does not require advanced results on holonomic series. In this section, our aim is to obtain a similar bound for the inclusion problem for weakly-unambiguous Parikh automata. The inclusion problem for RCM (and hence for weakly-unambiguous PA) is shown to be decidable in [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF] but no complexity bound is provided. Note that this problem is known to be undecidable for non-deterministic PA [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF]. We follow the same approach as for the rational case [START_REF] Stearns | On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata[END_REF] and for RCM [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF]. In stark contrast with the rational case, it is necessary to closely inspect holonomic closure properties in order to give concrete bounds. Fix A and B two weakly-unambiguous PA. We can construct a weakly-unambiguous PA C accepting L(A) ∩ L(B). We rely on the key fact that the series D(x) = A(x) -C(x) counts the number of words of length n in L(A) \ L(B). In particular, L(A) ⊆ L(B) if and only if D(x) = 0.

As D(x) is the difference of two holonomic series, it is holonomic. As equality between holonomic series is decidable, [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF] concludes that the problem is decidable. But without further analysis, no complexity upper-bound can be derived. The coefficients of D(x) = n≥0 d n x n satisfy a recurrence equation of the form p 0 (n)d n = r k=1 p k (n)d n-k for n ≥ r with p 0 (x) = 0. This equation fully determines d n in terms of its r previous values d n-1 , . . . , d n-r , provided that p 0 (n) = 0. In particular, if the r previous values are all equal to 0, then d n = 0. Consequently, if d n is equal to 0 for all n ≤ r + R where R denotes the largest positive root of p 0 (which is bounded from above by its ∞-norm, as a polynomial on Z) then15 D(x) = 0.

Taking W := r + R, we have that if L(A) ⊆ L(B) then there exists a word witnessing this non-inclusion of length at most W . We now aim at computing an upper-bound on W on the size of the inputs A and B.

For this, we first bound the order of the linear recurrence satisfied by A(x) and C(x), as well as the degrees and norm of the polynomials involved. This is stated in Proposition 22, whose proof follows the one of Proposition 12, while establishing such bounds for the multivariate Hadamard product and the specialization to 1.

Proposition 22.

The generating series A(x) of a weakly-unambiguous PA A of dimension d ≥ 1 satisfies a non-trivial linear differential equation q s (x)∂ s

x A(x) + • • • + q 0 (x)A(x) = 0, with s ≤ ((d + 1)|A| A ∞ ) O(d) and for all i ∈ [0, s], deg(q i ) ≤ ((d + 1)|A| A ∞ ) O(d) and log q i ∞ ≤ ((d + 1)|A| A ∞ ) O(d 2 ) using the notations of Section 3.2.

Finally, we transfer these bounds to the series D(x) of L(A) \ L(B) using the analysis of [START_REF] Kauers | Bounds for D-finite closure properties[END_REF] for the sum of holonomic series in one variable. Using the bound of Theorem 23, the inclusion problem can be solved in triply exponential time by a naive counting of all words up to the bound. Using dynamic programming to compute the number of accepted words, we can decide inclusion in doubly exponential time. Remark 25. In [START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF], the authors propose a different construction to prove the holonomicity of the generating series of languages in RCM. This proof uses the closure of holonomic series under Hadamard product and algebraic substitution x 1 = x 2 = • • • = x n = x. It is natural to wonder if this approach would lead to better bounds in Proposition 22 (using the equivalence between weakly-unambiguous PA and RCM). It turns out that the operation x 1 = x 2 = • • • = x n = x is more complicated than it seems at a first glance. Indeed, to our knowledge, no proof of the closure under algebraic substitution explains what happens if, during the substitution process, the equations become trivial. This issue can be overcome by doing the substitution step by step: x 2 = x 1 , then x 3 = x 1 , etc. However, this naive approach would produce worse bounds.

Perspectives

The bounds obtained in Section 5 are derived directly from constructions given in the proofs of the closure properties. In particular, we did not use any information on the special form of our series. The bounds are certainly perfectible using more advanced tools from computer algebra. Also it seems that the complexity of the closure under the algebraic substitution deserves more investigation, as discussed in Remark 25.

A more ambitious perspective is to find larger classes of automata whose generating series are holonomic. This would certainly require new ideas, as for instance any holonomic power series with coefficients in {0, 1} is known to be the characteristic series of some semilinear set [START_REF] Bell | Power series with coefficients from a finite set[END_REF].

  and the symmetric ones for the other variables x b and x c .

1 1 -

 1 xax b xc is the support series of the subset {(n, n, n) : n ∈ N}, and since 1 1-(xa+x b +xc) is the multivariate series of all the words on {a, b, c}, we have

Figure 1

 1 Figure 1 A weakly-unambiguous Parikh automaton accepting the language L = {c n w : w= x1x2 • • • xm ∈ {a, b} * ∧ m ≥ n > 0 ∧ |x1x2 • • • xn|a < |x1x2 • • • xn| b }over the alphabet {a, b, c} with the semilinear constraint {(n1, n2, n3) : n1 = n2 + n3 and n2 < n3}.

  If we fix an alphabet Γ = {a 1 , . . . , a d } with the ordering a 1 < • • • < a d on the letters, we can associate with every semilinear set C of dimension d, the language [C] = {w ∈ Γ * : (|w| a1 , . . . , |w| a d ) ∈ C} of words whose numbers of occurrences of each letter satisfy the constraint expressed by C. For instance, if we take the semilinear set C 0 = {(n, m, n, m) : n, m ≥ 0} and the alphabet {a, b, c, d} ordered by a < b < c < d, [C 0 ] consists of all words having as many a's as c's and as many b's as d's.

  C ⊆ N d and a length preserving morphism µ : Γ * -→ Σ * , that is injective over R∩[C], so that L = µ(R∩[C]). For example, L abab = {a n b m a n b m : n, m ∈ N} can be shown to be in RCM by taking Γ = {a, b, c, d}, Σ = {a, b}, µ(a) = µ(c) = a, µ(b) = µ(d) = b, R = a * b * c * d * and the semilinear set C 0 defined in the previous paragraph. Theorem 14. L ∈ RCM iff L is recognized by a weakly-unambiguous Parikh automaton.

  Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Theorem 23 .

 23 Given two weakly-unambiguous PA A and B of respective dimensions d A and d B , if L(A) is not included in L(B) then there exists a word in L(A) \ L(B) of length at most 2 2 O(d 2 log(dM )) where d = d A + d B and M = |A| |B| A ∞ B ∞ .

Corollary 24 .

 24 Given two weakly-unambiguous PA A and B of dimensionsd A and d B , we can decide if L(A) is included in L(B) in time 2 2 O(d 2 log(dM )) where d = d A + d B and M = |A| |B| A ∞ B ∞ .

The name RCM comes from the fact that these languages are defined using a Regular language, a semilinear Constraint and a Morphism.

We use the term weakly-unambiguous here to avoid a possible confusion with the class of unambiguous PA defined in[START_REF] Cadilhac | Unambiguous constrained automata[END_REF] which is strictly contained in our class. Our notion of non-ambiguity is the standard one: every word has at most one accepting computation (this is detailed inRemark 11).

In this article, we use an equivalent definition where the transitions of the automaton are additionally labeled by vectors of natural numbers. A run is accepting if the sum of all the vectors encountered in the run satisfies a semilinear constraint.

The generalization of this equivalence to the multivariate case is not straightforward (see[START_REF] Lipshitz | D-finite power series[END_REF] for more details) and will not be used in this article.

Note that the substitution of a power series into another power series might not yield a power series: for instance substituting x by 1 + y in n≥0 x n does not result in a power series as the constant term would be infinite.

114:6 Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

In[START_REF] Massazza | Holonomic functions and their relation to linearly constrained languages[END_REF], LCL is defined without the injective morphism but we adapt it following[START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF].

Using deterministic context-free languages instead of unambiguous ones in the definition of LCL would result in the same class.

The proof of Theorem 7 in[START_REF] Castiglione | On a class of languages with holonomic generating functions[END_REF] wrongly suggests that we can take the order of the differential equation for D as a bound on the length of a witness for non-inclusion. In general, this is not the case. For instance consider D(x) = x 1000 which satisfies the first-order differential equation 1000D(x) -x∂xD(x) = 0. It is clear that the coefficients D0 = 0 and D1 = 0 are not enough to decide that D is not zero.


Bouffier Neso Laurent

Sojic

Quantum nuts: two shells are better than one to achieve highly efficient electrochemiluminescence

[Insert First Reactions Body Text Here]:

Developing bright and multicolor electrochemiluminescence (ECL) nano-emitters is widely pursued to achieve high sensitivity and multiplexing in bioassays and microscopy operating in physiological conditions. It is a particularly challenging task considering the specific requirements of charge injections and surface traps occurring in water during the ECL process. In this issue of ACS Central Science, Su, Peng, and coworkers rationalize the criteria of QDs architecture for ECL generation. [START_REF] Cao | Quantum Dots with Highly Efficient, Stable, and Multicolor Electrochemiluminescence[END_REF] In an exciting report, they present elegantly designed water-soluble QDs with an impressive ECL efficiency. ECL is the light emitted by the excited state of a luminophore upon an electrochemical reaction (i.e. without photoexcitation). [START_REF] Liu | Recent advances in electrochemiluminescence[END_REF] The initial electron-transfer reaction at the electrode surface triggers a cascade of reactions involving energetic intermediates that leads in fine to the formation of the excited state. It relaxes to the ground state and emits a photon. It is a powerful analytical technique with an extremely low background because it combines the orthogonal modalities of electrochemical stimulation and optical detection. Thus, ECL crystallizes the beauty and complexity from both electrochemistry and photophysics. ECL is successfully commercialized for a large number of immunoassays, such as for cardiac and infectious diseases, thyroid, tumor markers, etc. Almost 2 billion ECL-based assays for clinical diagnostics run worldwide each year. [START_REF] Cao | Quantum Dots with Highly Efficient, Stable, and Multicolor Electrochemiluminescence[END_REF] Since it is based on an optical readout, ECL has also evolved into a powerful imaging method. [START_REF] Zhang | Electrochemiluminescence-Based Capacitance Microscopy for Label-Free Imaging of Antigens on the Cellular Plasma Membrane[END_REF] Most of the applications still rely on the model [Ru(bpy) 3 ] 2+ or cyclometalated Ir(III) luminophores with a sacrificial coreactant species. [START_REF] Chen | A conceptual framework for the development of iridium(iii) complex-based electrogenerated chemiluminescence labels[END_REF] Many works have been carried out to improve the ECL efficiency in water. [START_REF] Zanut | Insights into the mechanism of coreactant electrochemiluminescence facilitating enhanced bioanalytical performance[END_REF] Indeed, brighter ECL emitters and various emission colors are highly desirable due to the increasing demand for accuracy and multiplexing in microscopy and diagnostics. Colloidal quantum dots (QDs), which are semiconductor nanocrystals (NCs) exhibit unique quantum size effects. Their electronic, optical, and electrochemical properties depend strongly on their size, shape and surface chemistry due to their very high surface area-to-volume ratio that may lead to various heterogeneous redox reactions with the surrounding environment. In a seminal work h y 2000' , Ding et al. reported the ECL from silicon QDs. [START_REF] Ding | Electrochemistry and Electrogenerated Chemiluminescence from Silicon Nanocrystal Quantum Dots[END_REF] After that, a large variety of semiconductor materials such as Ge, CdTe, CdSe, and PbSe have been explored to generate ECL. But, in most cases, surface reactivity can lead to the formation of electronic traps for electrons and holes, which strongly inhibit the ECL process by translating into poor efficiency. Indeed, depending on the semiconductor and its intrinsic f h m y h QD ' h m v y result in either disastrous characteristics or original useful performances. [START_REF] Hesari | Highly Efficient Dual-Color Electrochemiluminescence from BODIPY-Capped PbS Nanocrystals[END_REF] As nicely discussed in the article, [START_REF] Cao | Quantum Dots with Highly Efficient, Stable, and Multicolor Electrochemiluminescence[END_REF] ECL of QDs corresponds to a very different situation in comparison to photoluminescence (PL) and electroluminescence. In the ECL process (Figure 1a), the QDs diffuse freely in solution during the sequential injection events of electrons (heterogeneously, from the electrode) and holes (homogeneously, from the electrogenerated coreactant radical). Therefore, trapping of such injected charges by h QD ' f m gh b v y effective and lasts much longer than in PL or electroluminescence. Therefore, specific criteria for the design of water-soluble ECL-active QDs should be considered to avoid such surface traps for charge carriers. The article published now in ACS Central Science investigated the effects of the architecture and surface of QDs on the PL quantum yield (Φ PL ) in water, which impacts directly the ECL efficiency. [START_REF] Cao | Quantum Dots with Highly Efficient, Stable, and Multicolor Electrochemiluminescence[END_REF] The authors present a systematic PL and ECL study by preparing CdSe core QDs, CdSe/CdS core/shell QDs and finally CdSe/CdS/ZnS core/shell/shell QDs. They selected CdSe as the core material for the QDs because it has been reported to behave as a trap-free QDs with near-unity Φ PL in toluene and monoexponential PL decay dynamics. But, when converted to the water-soluble form through ligand exchange, CdSe core QDs became barely emissive in water. By contrast, the CdSe/CdS core/shell QDs with five monolayers of CdS shells show much larger Φ PL in water but still with surface trap issues. Therefore, the authors used the epitaxial ZnS shells with a very wide bandgap to isolate these traps from the photogenerated excitons in the QDs. The authors developed a new epitaxy scheme to eliminate possible defects and the resulting CdSe/CdS/ZnS QDs with three monolayers of the ZnS shells exhibit near-unity Φ PL and monoexponential PL decay dynamics in both toluene and water. The inner CdS shell is necessary because it functions as a buffer layer to relieve the lattice mismatch between CdSe and ZnS. This stepwise comparative structure-ECL activity study demonstrates that the CdSe/CdS/ZnS core/shell/shell QDs are extremely bright ECL nano-emitters in PBS. Nowadays, the metal coordination complex, [Ru(bpy) 3 ] 2+ , remains the gold standard in ECL, even if some cyclometalated Ir(III) luminophores challenge its performances. [START_REF] Fernandez-Hernandez | Photophysics and Electrochemiluminescence of Bright Cyclometalated Ir(III) Complexes in Aqueous Solutions[END_REF] The significance of this work is further emphasized by the fact that the optimized QDs with two tightly controlled shells show exceptional ECL performances. Indeed, their ECL efficiency is 6 orders of magnitude larger than that of the reference [Ru(bpy) 3 ] 2+ . This remarkably high value is due to several key factors: high Φ PL , short luminescence lifetime, centerlocalized charges, and large size of the QDs (i.e. from 5.9 nm up to 9.0 nm). In addition, by controlling the size of the CdSe core of the QDs, the ECL emission was tuned precisely from green to yellow and red when increasing the QDs size (Figure 1b). Finally, concomitant multicolor ECL emission from multiple QDs was readily achieved in aqueous media (Figure 1c). Such an ability to tune the ECL emission color(s) has recently generated a wide interest due to potential multiplexing applications. 9,10 This study also demonstrated clearly a key mechanistic element that has been proposed to enable the ECL process. Since ECL starts with an initial electron-transfer reaction, it was essential to prove the direct reduction of the QDs at the electrode surface (i.e. direct electron injection from the electrode to the conduction band of the QDs). For this, an original approach using fluoride-doped tin oxide (FTO) electrode surface modified with an ultrathin insulating silica nanochannel membrane (SNM) was elaborated (Figure 2). The diameter f h h w h g f 2-3 m whereas the diameter of the QDs was ~8 nm. Therefore, the QDs cannot reach the electrode surface and be reduced directly at the FTO surface. Only the persulfate coreactant, which is much smaller can diffuse through the channels of the SNM and reacts at the electrode surface. With the SNM, ECL intensity of the QDs was extremely low in comparison to the bare FTO electrode. This smart experiment demonstrates unambiguously the essential role of the direct electron injection from the electrode into the QDs to generate ECL. In a nutshell, the understanding of the ECL process with the crucial role of the charge injection allowed the authors to design water-soluble CdSe/CdS/ZnS core/shell/shell QDs. Such a structure with a CdSe core and a chemically-engineered double shell generates ECL light very efficiently (i.e. two shells are better than one). The reported approach provides a general methodology opening enticing perspectives for spectrally distinct detection of several analytes with improved sensitivity in multiplexed bioassays and ECL microscopy.

Figure 1 .

 1 Figure 1. (a) Schematic representation of the ECL process with the charge injection from the electrode and the sacrificial persulfate coreactant. (b) Spectrally-resolved multicolor ECL generation from CdSe/CdS/ZnS QDs with different core sizes. (c) 3D graphs of ECL-potential spectra of the ternary mixture of green-, yellow-, and red-emitting QDs. Reprinted with permission from ref 1. Copyright 2020 American Chemical Society.

Figure 2 .

 2 Figure 2. (a) Blocking effect of the electron injection from the FTO electrode to the QDs by the ultrathin SNM. (b) Top-view TEM image of the SNM. Reprinted with permission from ref 1. Copyright 2020 American Chemical Society.


Alin Bostan
email: alin.bostan@inria.fr

Manuel Kauers

Thibaut Verron

The generating function of Kreweras walks with interacting boundaries is not algebraic

Keywords: Enumerative combinatorics, generating functions, lattice paths, Kreweras walks, kernel method, computer algebra, creative telescoping, automated guessing, algebraic functions, D-finite functions, hypergeometric functions

studied generating functions of Kreweras walks and of reverse Kreweras walks in the quarter plane, with interacting boundaries. They proved that for the reverse Kreweras step set, the generating function is always algebraic, and for the Kreweras step set, the generating function is always D-finite. However, apart from the particular case where the interactions are symmetric in x and y, they left open the question of whether the latter one is algebraic. Using computer algebra tools, we confirm their intuition that the generating function of Kreweras walks is not algebraic, apart from the particular case already identified.

Introduction

It is always interesting to know whether a generating function is D-finite, because Dfiniteness gives easy access to a lot of useful information about the series. It is also interesting to know whether a D-finite series is algebraic, because algebraicity gives access to even more useful information or makes more efficient algorithms applicable.

Every algebraic series is D-finite but not vice versa, and it is a notoriously difficult problem to decide for a given D-finite power series whether it is algebraic or not [16, §4(g)].

There exists an algorithm for deciding whether a given linear differential equation has only algebraic solutions [START_REF] Michael | Algebraic solutions of nth order linear differential equations[END_REF]. This algorithm can be generalized in order to compute, for a given linear differential operator L, another differential operator L alg , whose solution space is spanned by the algebraic solutions of L [14]. The operator L alg can then be used to decide whether a specific solution y of L(y) = 0 is algebraic or transcendental. However, the algorithm for computing L alg is very expensive, and to our knowledge it was never implemented.

A popular and simple check is to inspect the asymptotic behaviour of the coefficient sequence: if it is not of the form cφ n n α with α ∈ Q \ Z <0 , then the series is transcendental [START_REF] Flajolet | Analytic models and ambiguity of context-free languages[END_REF]. However, this condition is only necessary but not sufficient. The purpose of this paper is to highlight a less popular condition which is also necessary but not sufficient, and which can be tried in many cases where the asymptotic test fails. The method consists in finding (using computer algebra) a closed form representation of the D-finite function in question and to prove (also using computer algebra) that the function has a logarithmic singularity.

Our method is an illustration of the guess-and-prove paradigm, which is classically used to prove algebraicity [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF]: one guesses an algebraic equation, then post-certifies it. Transcendence is a more difficult task, as one needs to prove that no algebraic equation exists. However, if one can still guess a differential equation, and solve it in explicit form, then the explicit solution can lead to transcendence proofs. This is the methodology promoted here. In order to facilitate its application to other examples, we include a detailed description of the required computer algebra calculations for Maple and Mathematica1 .

As a concrete example, we consider a power series that appears in a recent study of restricted lattice walk models with interacting boundaries. A model is determined by a step set S ⊆ {-1, 0, 1} 2 \ {(0, 0)} and consists of walks in the quarter plane N 2 starting at (0, 0). For each step set S, Beaton et al. [START_REF] Beaton | Exact solution of some quarter plane walks with interacting boundaries[END_REF][START_REF] Nicholas R Beaton | Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models[END_REF] are interested in the generating func- tions

Q(a, b, c, x, y, t) ∈ Q[[a, b, c, x, y, t]],
where [a h b v c u x i y j t n ]Q is the number of walks of length n starting at (0, 0) ending at (i, j), with h visits of the horizontal axis, v visits of the vertical axis, and u visits of the origin. Among other things, they show that the generating function is algebraic for the step set { , , } (known as reverse Kreweras), and that the generating function is D-finite for the step set { , , } (known as Kreweras). They conjecture that this latter series is not algebraic, and this is what we will prove here. More precisely, we will show the following:

Theorem 1. Let Q(a, b, c; x, y; t) ∈ Q[a, b, c][[x, y, t]
] be the generating function counting interactive Kreweras walks restricted to the quarter plane. The generating function Q(a, b, c; x, y; t) is not algebraic over Q(a, b, c, x, y, t).

Furthermore, for values a, b, c ∈ Q with c = 0, the generating function Q(a, b, c; x, y; t) ∈ Q[[x, y, t]] is algebraic over Q(x, y, t) if and only if a = b.

Notations and the kernel equation

We first recall some notations used in this paper. Whenever possible, we follow the notations used in [START_REF] Nicholas R Beaton | Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models[END_REF]. Let R be an integral domain with fraction field K. We denote:

• R[t] the ring of polynomials in t with coefficients in R;

• K(t) the field of rational functions in t with coefficients in K, which is the fraction field of R[t];

• R[t, 1/t] the ring of Laurent polynomials in t with coefficients in R;

• R[[t]] the ring of formal power series in t with coefficients in R.

Given f (t) ∈ K((t)), we denote by [t n ] f the coefficient of t n in f (t), so that f (t) = ∑ n∈Z ([t n ] f )t n . We denote by [t > ] f the sum of the terms of f with positive exponents, that is, [t > ] f = ∑ n∈Z >0 ([t n ] f )t n .
We denote by R[t] ∂ t the Ore algebra of differential operators in t with polynomial coefficients. It is a non-commutative ring, and it has a left-action on the rings above, given by ∂ t ( f ) = ∂ f ∂t . Those definitions can be iterated to extend them to multiple variables, and we group together the brackets when applicable: for example R[[x, y]] is the ring of formal power series in x, y with coefficients in R, and given f ∈ R[[x, y]], we denote by [x > y 0 ] f the sum of terms of positive degree in x and degree 0 in y in f . For n, k, l, h, v, u ∈ Z, we denote by q h,v,u;k,l;n the number of walks of length n which:

• start at (0, 0);

• end at (k, l);

• never leave the upper-right quadrant {(x, y) ∈ Z 2 : x ≥ 0, y ≥ 0};

• visit the horizontal boundary (excluding the origin) {(x, y) ∈ Z 2 : x > 0, y = 0} exactly h times;

• visit the horizontal vertical boundary (excluding the origin) {(x, y) ∈ Z 2 : x = 0, y > 0} exactly v times;

• visit the origin u times (not counting the starting point).

The associated generating function Q(a, b, c; x, y; t) is defined as

Q(a, b, c; x, y; t) = ∑ n t n ∑ k,l x k y l ∑ h,v,u q h,v,u;k,l;n a h b v c u .
Note that, since there are only finitely many walks of a given length, for each n, the two innermost sums define a polynomial. Hence Q(a, b, c; x, y; t)

lives in Q[a, b, c, x, y][[t]] ⊂ Q[a, b, c][[x, y, t]].
For shortness, we shall write Q(x, y) := Q(a, b, c; x, y; t). In particular, Q(0, 0) is the generating function counting interacting walks ending at (0, 0), Q(x, 0) is the generating function counting interacting walks ending on the horizontal axis and Q(0, y) is the generating function counting interacting walks ending on the vertical axis. Finally, we denote by

Q i,j = Q i,j (a, b, c; t) := [x i y j ]Q(x, y) ∈ Q[a, b, c][[t]
] the generating function counting interacting walks ending at point (i, j). The coefficient of t n in Q i,j is a polynomial in a, b, c, and its coefficient for the monomial a h b v c u is exactly q h,v,u;k,l;n .

The elements a, b, c are called weights associated respectively to the horizontal boundary (excluding the origin), the vertical boundary (excluding the origin) and the origin.

Given a step set S ⊆ {-1, 0, 1} 2 \ {(0, 0)}, the step generator S is S(x, y) = ∑ (i,j)∈S x i y j ∈ Q[x, 1/x, y, 1/y].
We denote by • A(x, y) = ∑ (i,-1)∈S x i y -1 the step generator for the steps going southwards;

• B(x, y) = ∑ (-1,j)∈S x -1 y j the step generator for the steps going westwards;

• G(x, y) = x -1 y -1 if (-1, -1) ∈ S and 0 otherwise, the step generator for the steps going south-westwards.

The kernel of the step set is

K(x, y) = 1 -tS(x, y) ∈ Q[t, x, 1/x, y, 1/y].
The kernel equation is a functional equation satisfied by the generating function counting walks restricted to the quarter plane.

Theorem 2 ([2, Theorem 1]). For a lattice walk restricted to the quarter-plane, starting at the origin, with weights a (resp. b) associated with vertices on the x-axis excluding the origin (resp. the y axis excluding the origin), and weight c associated with the origin, the generating function Q(x, y) satisfies the following functional equation

K(x, y)Q(x, y) = 1 c + 1 a (a -1 -taA(x, y)) Q(x, 0) + 1 b (b -1 -tbB(x, y)) Q(0, y) + 1 abc (ac + bc -ab -abc) + tG(x, y) Q(0, 0). (2.1)
3 Main result and the power series Θ

We consider specifically the Kreweras step set S = {(1, 1), (-1, 0), (0, -1)}.

+ bc t 3 + • • • .
For instance, at length 3, the walk (0, 0) → (1, 1) → (2, 2) → (3, 3) corresponds to the term a 0 b 0 c 0 x 3 y 3 t 3 = x 3 y 3 t 3 , as it does not touch any of the axes after leaving the origin, while the walk (0, 0) → (1, 1) → (1, 0) → (0, 0), corresponds to a 1 b 0 c 1 t 3 x 0 y 0 = act 3 , as after leaving the origin it touches the positive horizontal axis once, it returns to the origin once, but does not touch the positive vertical axis.

The main result of this paper is that Q is not algebraic (Theorem 1). In order to prove it, we define

Θ = [x > y 0 ] (x -y)(x 2 y -1)(xy 2 -1) xyK(x, y) , ( 3.1)
where K(x, y) = 1t xy + x -1 + y -1 . We will prove that Θ is not algebraic. The connection between Θ and Q comes from the following lemma.

Lemma 3 ([2, Lemma 10]). There exist Laurent polynomials β, β x,0 , β 0,x , β 0,0 , β 1,0 , β 2,0 ,

β 3,0 ∈ Q[t, 1/t, x, 1/x], such that β + β x,0 Q(x, 0) + β 0,x Q(0, x) + β 0,0 Q(0, 0) + β 1,0 Q 1,0 + β 2,0 Q 2,0 + β 3,0 Q 3,0 = t 3 a -b c (ab -(ab -ac -bc + abc)Q(0, 0))Θ. (3.2)
Proof. It is a straightforward transposition of [2, Lemma 10], by observing that with the notations therein, θ = t 3 a-b c abΘ and θ 0,0 = t 3 a-b c (abacbc + abc)Q(0, 0)Θ.

Transcendence of Θ

Recall that for α, β, γ ∈ Q and -γ / ∈ N, the Gaussian hypergeometric series 2 F 1

α, β γ ; t is defined as 2 F 1 α, β γ ; t := ∞ ∑ n=0 (α) n (β) n (γ) n t n n! ∈ Q[[t]],
where (u) n denotes the Pochhammer symbol (u

) n = u(u + 1) • • • (u + n -1) for n ∈ N. It satisfies the differential equation t 2 -t y ′′ (t) + ((α + β + 1)t -γ) y ′ (t) + αβ y (t) = 0.
Theorem 4. The power series Θ defined in (3.1) admits the following closed form representation:

Θ(t; x) = A 1 (t; x) + A 2 (t; x) t 0 A 3 (s; x)T(s; x)ds,
where

A 0 = 1 - 2t x -(4x 3 -1) t 2 x 2 , A 1 = 1 6xt 3 - x 3 -1 2x 2 t 2 + 2 -3x 3 6x 3 t + tx 3 + 2t -x 6t 3 x 2 A 0 , A 2 = x 2 (x -tx 3 -2t) 3t 3 A 0 , A 3 = 1 (tx 3 + 2t -x) 2 (4t 2 x 3 -(x -t) 2 )A 0 , T = (3t -x)x 2 F 1 -1/3, -2/3 1 ; 27t 3 + 4t(2tx 3 + t -x) 2 F 1 -1/3, 1/3 2 ; 27t 3 .
The power series A 0 , A 1 , A 2 and A 3 are algebraic, and the power series T is transcendental. In particular, Θ is transcendental.

Proof. We prove that Θ is equal to C := A 1 + A 2 A 3 T, in four steps:

1. use creative telescoping [START_REF] Chyzak | An extension of Zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Koutschan | A fast approach to creative telescoping[END_REF] to obtain a differential operator L ct ∈ Q(x, t) ∂ t annihilating Θ;

2. verify that L ct annihilates C;

3. find r ∈ N such that if s ∈ Q(x)[[t]
] is a power series solution of L ct and s = 0 mod t r , then s = 0;

4. verify that Θ and C, both power series solution of L ct , are equal modulo t r and so they are actually equal.

For the first step, define

Θ 0 (t; x, y) = (x -y)(x 2 y -1)(xy 2 -1) xyK(x, y) ∈ Q(x, y, t) so that Θ = [x > y 0 ]Θ 0 .
In order to bring the problem to a form suitable to creative telescoping algorithms, we encode the coefficient extractions as residues. Extracting the constant coefficient in y is immediate: for any

F ∈ Q[x, 1/x, y, 1/y][[t]],
as by definition,

[y 0 ]F(t; x, y) = Res y=0 F(t; x, y) y ∈ Q[x, 1/x][[t]].
For extracting the positive part, we follow [4, Theorem 3]: for any

F ∈ Q[x, 1/x][[t]], [x > ]F(t; x) = Res z=0 1 z F(t; z) x z 1 -x z ∈ Q[x][[t]].
So composing the two, we get

Θ(t; x) = Res z=0 Res y=0 1 yz Θ 0 (t; z, y) x z 1 -x z . ( 4.1)
An annihilator for this can now be computed using creative telescoping, for example, using the Mathematica package HolonomicFunctions

t]}]], Der[z], {Der[t]}]]]

This yields an operator L ct ∈ Q(x, t) ∂ t of order 6, which annihilates Θ.

Checking that L ct annihilates C is a straightforward computation with a computer algebra software. For instance, in Maple, the following command evaluates to 0: # In Maple with(DEtools); simplify(eval(diffop2de(Lct, [Dt,t], y(t)), y(t) = C));

For the last step, we need to look at a basis of power series solutions of L ct . Computer algebra software can again be used to compute (truncations of) elements in such a basis. For instance, this can be done with the following lines in Maple.

# In Maple

Order := 8; sols := formal_sol(Lct,[Dt,t]); # Keep only the power series solutions sols := select(s -> type(series(s,t=0),'taylor'), sols);

The output shows that the set of power series solutions is a Q(x)-vector space of dimension 2 spanned, after a change of basis bringing the first terms to echelon form, by

s 0 = 1 + xt 2 + t 3 + O(t 4 ), s 1 = t + 1 -x 3 x t 2 + 1 x 2 t 3 + O(t 4 ).
So a power series solution of L ct is entirely determined by its coefficients of degree 0 and 1, and in particular knowing a power series modulo t 2 is enough. Finally, checking that the first two coefficients of C and Θ are equal is again a straightforward computation. For instance, again using Maple: # In Maple map(normal,series(C,t,5)); series(Theta,t,2); returns the same result -x 2 + O(t 2 ). This allows to conclude that Θ = C.

For the second statement of the theorem, note that A 0 , A 1 , A 2 and A 3 are algebraic by closure properties of algebraic functions. The proof of the fact that T is transcendental combines human observation and computer algebra. First, observe that if T(t; x) was algebraic, then by closure properties so would be T(t; 3t), which has only one hypergeometric term, and thus H(t) = 2 F 1 -1/3,1/3 2 ; t would be algebraic. But it is straightforward to verify that this cannot be the case, either by a lookup in Schwarz's classification of algebraic 2 F 1 's [START_REF] Schwarz | Ueber diejenigen Fälle, in welchen die Gaussische hypergeometrische Reihe eine algebraische Function ihres vierten Elementes darstellt[END_REF], or simply by observing that the minimal-order linear differential equation 9t 2 -9t H ′′ (t) + (9t -18) H ′ (t) -H (t) = 0 of H has solutions which cannot be algebraic because one of them has logarithms in its local expansion at 0.

Finally, it follows that Θ is also transcendental, again by closure properties: if Θ was algebraic, so would be t 0 A 3 (s; x)T(s; x)ds, and so would be its derivative A 3 T, and so would be T.

We now give some more explanation on the process we followed to find the closed form proved above. The first step is to compute a small-order differential operator annihilating Θ. It is possible, given the data of the series coefficients, to guess such an operator L g of order 4 (hence smaller in order than L ct ), by using for instance the guesser [START_REF] Kauers | Guessing handbook[END_REF]:

(* In Mathematica, continuation of the previous calculations *) << "Guess.m" Theta = Expand[x*Expand[1/x CoefficientList[Series[Theta0,{t,0,70}],t]] /. (x^i_ /; i<0) -> 0 /. (y^i_ /; i!=0) -> 0]; Lg = GuessMinDE[Theta,TT[t]]
The output is an operator L g ∈ Q(x, t) ∂ t which is likely to annihilate Θ. We can increase our trust in this operator by verifying that L g right-divides L ct :

(* In Mathematica, continuation of the previous calculations *) OreReduce[Lct,{ToOrePolynomial[Lg,TT[t]]}]
This line returns the right-remainder of L ct modulo L g , which is 0 as expected.

At this point, we could also compute the quotient, and, examining its solutions similarly to what was done in the proof of Theorem 4, prove that L g annihilates Θ. But this is not necessary: the constructed closed form will (by design) be annihilated by L g , so the fact that L g is an annihilator of Θ is a consequence of the theorem.

As a next step, we compute a closed form solution C of L g . The starting point is to decompose L g as the least common left multiple (LCLM) of two operators of smaller order [START_REF] Mark Van Hoeij | Rational solutions of the mixed differential equation and its application to factorization of differential operators[END_REF]:

# In Maple L1, L3 := op(DFactorLCLM(Lg, [Dt,t]));
The output is a pair of two operators L 1 of order 1, and L 3 of order 3, such that L g = LCLM(L 1 , L 3 ). Equivalently, in terms of solution spaces, this means that a basis of solutions of L g (y) = 0 is obtained by the union of the bases of L 1 and L 3 , respectively. The operator L 1 admits a simple solution; this can be seen using the Maple command dsolve(diffop2de(L1, [Dt,t], y(t)), y(t)); which outputs 3

x 3 t + 3 x 4 t 2 - 2 t + 3 x t 2 -
x2 t 3 . It remains to treat the operator L 3 . The starting point is to decompose it as the product of two operators of smaller order [START_REF] Mark Van Hoeij | Factorization of differential operators with rational functions coefficients[END_REF]:

# In Maple fac := DFactor(L3, [Dt,t]);
The output is a pair fac = [L 2 , S 1 ] of two operators of order 2, respectively 1, such that L 3 = L 2 S 1 . Now the differential equation L 3 (z) = 0 is equivalent to L 2 (y) = 0 and S 1 (z) = y. Hence, it remains to solve L 2 (y) = 0. This can be done by using the algorithm in [START_REF] Jung | Second order differential equations with hypergeometric solutions of degree three[END_REF] and its Maple implementation provided by the authors 2 . Using the command hypergeomdeg3, one gets a solution in terms of hypergeometric 2 F 1 functions:

SOL:=x/t^3/(t*x^3+2*t-x)/(4*t^2*x^3-t^2+2*t*x-x^2)* ((x-3*t)*x*hypergeom([-1/3, -2/3],[1],27*t^3) -4*t*(2*t*x^3+t-x)*hypergeom([-1/3, 1/3],[2],27*t^3));
One can check that this is indeed a solution of L 2 ; indeed, the simplification command simplify(eval(diffop2de(fac [START_REF] Beaton | Exact solution of some quarter plane walks with interacting boundaries[END_REF], [Dt,t], y(t)), y(t) = SOL)); return 0. Moreover, one can show that this solution coincides (locally at t = 0) with the unique power series solution of L 2 . Finally, the solution of L 3 (z) = 0 can be found using simplify(dsolve( diffop2de(fac [START_REF] Nicholas R Beaton | Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models[END_REF], [Dt,t], z(t) ) = SOL, z(t))); which yields

tx 3 + 2t -x t 3 (4x 3 -1) t 2 + 2tx -x 2 SOL • t 3 tx 3 + 2t -x 1 (4x 3 -1) t 2 + 2tx -x 2 dt + c ,
where SOL is the hypergeometric expression found above and c = c(x) is a constant function in t, that is found by fitting initial terms of the power series expansions. Putting pieces together yields the expression in the statement of Theorem 4. Note that the method sketched above is rigorous in the sense that the closed form solution of L ct found in this way is correct by construction. The alternative correctness argument in the proof of the theorem is independent of how the closed form was found.

5 Transcendence of Q Theorem 5. Assume that a = b and c = 0. In particular, this is the case if a, b, c are variables in the polynomial ring Q[a, b, c]. Then the power series Q(x, y), Q(x, 0) and Q(0, y) are transcendental over Q(a, b, c, x, y, t).

Proof. First note that the algebraicity of the three series is equivalent: if Q(x, y) is algebraic, then so are its specializations Q(0, y) and Q(x, 0); and conversely, if, say, Q(0, y) is algebraic, then by symmetry of the step set so is Q(x, 0), and by the kernel equation, so is Q(x, y).

To reach a contradiction, assume that Q(x, y) is algebraic. Then, by taking the derivative along x and taking the value at x = y = 0, the power series Q 1,0 is also algebraic. Repeating the same process, Q 2,0 and Q 3,0 are algebraic. Recall that Q(0, 0) is algebraic [2, Corollary 3]. So all in all, the left-hand side L of Equation (3.2) is algebraic.

If (a -b) ab -(ab -ac -bc + abc)Q(0, 0) = 0, this would imply that Θ = c L (a -b) ab -(ab -ac -bc + abc)Q(0, 0) t 3
is also algebraic, which is a contradiction with Theorem 4. Thus, (ab) ab -(abacbc + abc)Q(0, 0) = 0. By assumption, a = b, so the second factor has to be zero. Since Q(0, 0) = 1 + (a + b)ct 3 + • • • , extracting coefficients of t 0 and t 3 in this second factor yields abc = ac + bc and 0 = ab(a + b)c. Since c = 0, these relations imply ab = a + b and 0 = ab(a + b), thus ab = a + b = 0, and finally a = b = 0, which contradicts the assumption a = b.

Particular cases and additional remarks

If a = b, as observed in [2, Section 5.5], the right-hand side of Equation (3.2) vanishes, and then the series Q(x, y) is algebraic. If c = 0, then in particular Q(0, 0) = 1, and both sides of Equations (3.2) and (2.1) (after clearing out the denominator c) vanish. We do not know if the power series Q(x, y) is algebraic or even D-finite in that case. With sample values of a, b, x, y and c = 0, we were not able to guess any algebraic, differential or recurrence relation with the first 10 000 coefficients in t of the series Q(a, b, c; x, y; t).

The generating function Q(1, 1), which counts interacting walks regardless of their ending point, is also of interest, besides Q(0, 0) and Q(x, y). Experimentally, this generating function appears to be algebraic: for hundreds of thousands of triples (a, b, c) ∈ F 3 45007 , with F 45007 the finite field with 45007 elements, we could guess a polynomial P a,b,c (t, u) ∈ F 45007 [t, u] of degree 92 in t and degree 24 in u with P a,b,c (t, Q(a, b, c; 1, 1; t)) = 0 mod t 2350 . The next step would be to lift it to a polynomial P(a, b, c; t, u) ∈ Q[a, b, c, t, u] and to prove that P(a, b, c; t, Q(a, b, c; 1, 1; t)) = 0. In principle, this is doable using (a variant of) the approach in [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF].

  [START_REF] Koutschan | Advanced Applications of the Holonomic Systems Approach[END_REF], with the following:(* InMathematica *) << "HolonomicFunctions.m" Theta0 = (x-y)*(x^2*y-1)*(x*y^2-1)/(x*y*(1-t*(1/x+1/y+x*y))) Theta0z = Theta0 /. x -> z Lct = First[First[CreativeTelescoping[ First[CreativeTelescoping[Theta0z/z/y * (x/z)/(1-x/z), Der[y], {Der[z],Der[

  + xy t + x 2 y 2 + ax + by t 2 + x 3 y 3 + (a + 1)x 2 y + (b + 1)xy 2 + ac

	By exhaus-
	tive enumeration, the generating function Q(a, b, c; x, y; t) ∈ Q[a, b, c, x, y][[t]] starts
	1

Also available online: http://www.algebra.uni-linz.ac.at/research/kreweras-interacting

https://www.math.fsu.edu/~vkunwar/hypergeomdeg3/hypergeomdeg3

Acknowledgements

We warmly thank Mark van Hoeij for his advice, and for his precious help with the package hypergeomdeg3, especially in the parametric case.

; supported by the French ANR grant DeRerumNatura, ANR-19-CE40-0018. † manuel.kauers@jku.at; supported by the Austrian FWF grants F5004 and P31571-N32. ‡ thibaut.verron@jku.at; supported by the Austrian FWF grants F5004 and P31571-N32.