On the generating functions of languages accepted by deterministic one-reversal counter machines Paolo Massazza1 Università degli Studi dell’Insubria, Dipartimento di Scienze Teoriche e Applicate - Sezione Informatica, Via Mazzini 5, 21100 Varese, Italy paolo.massazza@uninsubria.it Abstract. We prove that the generating function of a language accepted by a one-way deterministic one-reversal counter machine without nega- tive cycles is holonomic. The result is achieved by solving a particular case of the conjecture LDFCM ( RCM. Here, RCM is a class of languages that has been recently introduced and that admits some interesting prop- erties, namely it contains only some particular languages with holonomic generating function. 1 Introduction A well-known result of Chomsky-Schützenberger [4] states that the generating functions of regular languages are rational whereas the generating functions of unambiguous context-free languages are algebraic. This fact allows us to use analytic methods to determine properties of languages. For example, a method to show that a context-free language L is inherently ambiguous, employed by Flajolet in [5] and [6], consists of proving that the generating function of L is transcendental. It is then interesting to look for classes of languages with generating functions that belong to classes of functions whose properties can be exploited for solving classical problems in language theory. In this context, holonomic functions have been widely investigated since the end of 1980s. The class of holonomic functions in one variable is an extension of the class of algebraic functions, and it contains all functions satisfying a ho- mogeneous linear differential equation with polynomial coefficients (see [12, 13]). Holonomic functions were first used in the context of formal languages in [1], where the authors proved that the problem of deciding the holonomicity of the generating function of a context-free language is equivalent to the problem of deciding whether a context-free language is inherently ambiguous. Furthermore, a class of languages with holonomic generating functions, called LCL, was in- troduced in [10] by means of linear constraints on the number of occurrences of symbols of the alphabet. A particular subclass LCLR ( LCL was also studied in [1]. The idea of using constraints and finite state automata in order to define languages is also at the basis of a family of automata called Parikh Automata and defined in [8, 9]. In particular, the subclass LPA of Parikh Automata on let- ters has been defined in [2] (actually, as noted in [3], LLPA = LCLR ). Recently, in [3] a wider class of languages with holonomic generating functions, called RCM, has been defined. This class of languages is contained in LNFCM , i.e. the class of languages recognized by nondeterministic one-way reversal bounded counter machines, whereas it is not contained in LDFCM , i.e. the class of languages rec- ognized by deterministic one-way reversal bounded counter machines [7]. Lastly, in [3] the conjecture LDFCM ( RCM has been stated. In this paper we prove that the conjecture is true for the subclass LDFCM6 consisting of the languages accepted by deterministic one-reversal counter ma- chines without negative cycles (informally, on reading a symbol the automaton can decrement a counter by a value bounded by a constant). The result is ob- tained by generalizing the technique used in [11], where it is proved that the class LDFCM(1,0,1) of languages accepted by deterministic counter machines with one-way input tape and one counter that is one-reversal bounded is contained in RCM. We recall that for any class of languages L, the relation L ⊆ RCM implies that the generating function of a language in L is holonomic. This provides a method for proving that a language L is not in L, which resembles in some sense the Flajolet methodology, used when L is the class of unambiguous context free languages. 2 Preliminaries In this section we give some basics about languages, classes of languages and au- tomata of our interest in the paper. Let Σ = {σ1 , σ2 , . . . , σh } be a finite alphabet and w ∈ Σ ? . For all σ ∈ Σ we indicate P by |w|σ the number of occurrences of σ in w. The length of w is |w| = σ∈Σ |w|σ . The prefix of w consisting of the first h symbols is w≤h . Similarly, w>h is the suffix of w starting at h + 1. Given two finite alphabets Γ and Σ, a morphism µ : Γ ? 7→ Σ ? is said to be length preserving if for all w ∈ Γ ? one has |µ(w)| = |w|. In particular, we are interested in length preserving morphisms that are injective on a fixed language L ⊆ Γ ? , that is, morphisms µ such that v 6= w implies µ(v) 6= µ(w). For any k > 0, we also consider a morphism κ : Nk 7→ {0, 1}k defined by κ(i) = 1 if i 6= 0 and κ(0) = 0. From here on, boldface symbols indicate tuples of integer values, and c[i] denotes the i-th element of c. Furthermore, if c, d ∈ Nk , then c + d is the their sum (componentwise). Linear constraints on the number of occurrences of symbols in an alpha- bet have been used in [10, 3] to define two classes of languages with holonomic generating functions, called LCL and RCM, respectively. Definition 1 (linear constraint). A linear constraint on the occurrences of symbols of Γ = {γ1 , γ2 , . . . , γh } in w ∈ Γ ? is an expression of the form h X ci |w|γi 4 ch+1 , with ci ∈ Z, 4 ∈ {<, ≤, =, 6=, ≥, >}. i=1 Definition 2 (system of linear constraints). A system of linear constraints C is either a linear constraint, or C1 ∨ C2 or C1 ∧ C2 or ¬C1 , where C1 and C2 are systems of linear constraints. We denote by [C] the language consisting of the words in Γ ? that satisfy the system of linear constraints C. Let L be a language on Γ , C a system of linear constraints on the number of occurrences of symbols in Γ and µ : Γ ? 7→ Σ ? a morphism. We indicate by hL, C, µi the language µ(L ∩ [C]) ⊆ Σ ? . In [3] the class of languages RCM has been defined as follows. Definition 3 (RCM). RCM is the class of languages hR, C, µi where R is a regular language on an alphabet Γ , C a system of linear constraints on Γ and µ : Γ ? 7→ Σ ? a length preserving morphism that is injective on R ∩ [C]. The class RCM admits several interesting properties. Indeed, it is closed under union and intersection, and it contains languages with holonomic generating function. Moreover, most of the classical decision problems (i.e. equivalence, inclusion, disjointness, emptiness, universe) are decidable for RCM, see [3]. 2.1 Counter machines In Section 4, the class RCM will be compared to the class of languages ac- cepted by a particular family of counter machines. We recall that a two-way k-counter machine is a finite automaton equipped with k counters. The opera- tions admitted on a counter are the increment or the decrement by 1, as well as the comparison with 0. The machine is called l-reversal bounded (l-reversal for short) if the count in each counter alternately increases and decreases at most l times. We refer to [7] for all definitions and for main results concern- ing the class DFCM(k, m, n) of deterministic (m, n)-reversal bounded k-counter machines, that is, n-reversal k-counter machines with a two-way input tape, where the input head reverses direction at most m times. In particular, we are interested in the class DFCM(k, 0, 1) where the input tape is one-way and the counters can change from increasing to decreasing mode at most once. Formally, a machine M ∈ DFCM(k, 0, 1) is a 7-tuple M = (k, Q, Σ, $, δ, q̇, F ), where k indicates the number of counters, Q is a finite set of states, Σ is the input al- phabet, $ is the right end-marker, δ is the transition function, q̇ ∈ Q is the initial state and F ⊆ Q is the set of final states. The transition function is a mapping from Q × (Σ ∪ {$}) × {0, 1}k into Q × {S, R} × {−1, 0, +1}k such that if δ(q, a, c1 , . . . , ck ) = (p, d, d1 , . . . , dk ) and ci = 0 for some i, then di has to be nonnegative to prevent negative values in a counter. The symbols S and R are used to indicate the movement of the input tape head (S = stay, R = right). A configuration of M is a triple (q, x$, c) where q ∈ Q, x ∈ Σ ∗ is the unread suffix of the input word, and the content of the k counters is c ∈ Nk . The transition relation on the set of configurations is denoted by →, and its reflexive ∗ and transitive closure by →. Hence, we write (p, v, c) → (q, z, c0 ) if and only if 0 δ(p, σ, κ(c)) = (q, b), c = c + b and either v = σz (if d = R) or z = v (if d = S). We are also interested in the relation ⇒, called one-symbol transition. Definition 4 (⇒). Let M = (k, Q, Σ, $, δ, q̇, F ) ∈ DFCM(k, 0, 1). For any x ∈ Σ ? and σ ∈ Σ we write (p, σx$, c) ⇒ (q, x$, c0 ) if and only if p, q ∈ Q, and either δ(p, σ, κ(c)) = (q, R, d) with c0 = c + d, or Pδ(p, σ, κ(c)) = (q1 , S, d1 ), δ(q1 , σ, κ(c + d1 )) = (q 2 , S, d2 ), . . . , δ(q h , S, κ(c + i=1..h di )) = (q, R, dh+1 ), with c0 = c + i=1..h+1 di . P Notice that the transition (p, σx$, c) ⇒ (q, x$, c0 ) uniquely identifies a sequence {di } of tuples in {−1, 0, 1}k and a sequence {qi } of states in Q. A sequence of |w| |w| one-symbol transitions reading a word w is shortened as (p, wx$, c) ⇒ (q, x$, c0 ). |w| ∗ A word w ∈ Σ ? is accepted by M if and only if (q̇, w$, 0k ) ⇒ (p, $, c) → (q, $, c0 ), for some q ∈ F and suitable c, c0 ∈ Nk .The language accepted by M , denoted by L(M ), is the set of all words accepted by M . Without loss of generality, we suppose that M always terminates and has only one final state, denoted by q̈, and that a word is accepted with all the counters equal to 0. The only accepting configuration is then (q̈, $, 0k ). In the following, we consider only deterministic 1-reversal counter machines that do not admit negative cycles. This class of machines is denoted by DFCM6 (k, 0, 1). Definition 5 (negative cycle). Let M = (k, Q, Σ, $, δ, q̇, {q̈}) be a counter machine in DFCM(k, 0, 1). Then, M has a negative cycle if there exists a se- quence of states q1 , . . . , qh ∈ Q, a symbol σ ∈ Σ and a suitable b ∈ {0, 1}k such that: – δ(q1 , σ, b) = (q2 , S, d1 ), δ(q2 , σ, b) = (q3 , S, d2 ), . . . , δ(qP h , σ, b) = (q1 , S, dh ) – d[l] < 0 for at least one l, with 1 ≤ l ≤ k, where d = i=1..h di ; – if d[l] < 0 then b[l] = 1 and di [l] ≤ 0 for all i; – if d[l] > 0 then b[l] = 1 and di [l] ≥ 0 for all i; – if d[l] = 0 then di [l] = 0 for all i; The k-tuple d is called the weight of the cycle. In a machine M ∈ DFCM6 (k, 0, 1), the effect on the counters of any one-symbol transition is bounded. More precisely, the following lemma holds. Lemma 1. Let (k, Q, Σ, $, δ, q̇, {q̈}) ∈ DFCM6 (k, 0, 1). Then, for any one-symbol transition (p, σx$, c) ⇒ (q, x$, c + d) one has 0 ≤ |d[l]| ≤ (3k + 1)|Q| for all l, with 1 ≤ l ≤ k. In particular, a counter machine that always terminates can not have a positive cycle (defined as in Def. 5, with the only difference that for all i and l one has di [l] ≥ 0, and d[l] > 0 for at least one l). At each step of the computation of a deterministic 1-reversal k-counter ma- chine, each counter is exactly in one of four different states, denoted by a value in the set U = {0, 1, 2, 3} and called the global state of the counter. More precisely, 0 is associated with a zero counter that has not been increased yet, 1 is associated with a counter that has been increased but not decreased, 2 is associated with a counter that has been increased and decreased and it is still greater than zero and, finally, 3 is associated with a counter that has been increased and decreased and it is equal to zero. Obviously, the global state of a counter may change from i to j, with i ≤ j, but not vice versa, hence the ordering 0 < 1 < 2 < 3 naturally arises. During a computation of a counter machine with k counters, a sequence of strings in U k is used to represent the evolution of the global states of the counters. The set U k is equipped with a partial order ≺, which is defined as follows: given α, β ∈ U k , define α ≺ β if and only if α[i] ≤ β[i] for all i with 1 ≤ i ≤ k. So, if α0 , α1 , . . . , αr is the sequence of global states of the counters of a machine that reads an input word w ∈ Σ ? , then one has α0 ≺ α1 · · · ≺ αr , with α0 = 0k (and αr ∈ {3, 0}k if w is accepted). Since the machine is reversal, there are at most 3k + 1 different global states in the sequence α0 , α1 , . . . , αr . In other words, in the poset (U k , ≺) any chain has a length which is smaller than or equal to 3k. Let ν : U k 7→ {0, 1}k be the morphism defined by ν(0) = ν(3) = 0 and ν(1) = ν(2) = 1. If α is the global state of the counters in a given configuration (q, σx$, c), then one has ν(α) = κ(c). A sequence {di } of tuples in {−1, 0, 1}k is called 1-reversal acceptable if and only if for all l, with 1 ≤ l ≤ k, one has that di [l] = −1 implies dj [l] ≤ 0 for all j > i. Moreover, {di } is compatible with α ∈ U k if it is 1-reversal acceptable and for all l, with 1 ≤ l ≤ k, one has: – if α[l] = 3 then ∀i di [l] = 0; – if α[l] = 2 then ∀i di [l] ≤ 0; – if α[l] = 0 then |{i|di [l] = −1}| ≤ |{i|di [l] = 1}|. Furthermore, given α, β ∈ U k with α ≺ b, we say that a sequence {di }, changes α into β if it is compatible with α and for all l, with 1 ≤ l ≤ k, the conditions in the following table hold (a dash indicates a case that can not occur, rl = |{i|di [l] = −1}|, sl = |{i|di [l] = 1}|). A sequence {di } that changes α into α is called stable w.r.t. α. β[l] = 0 β[l] = 1 β[l] = 2 β[l] = 3 α[l] = 0 rl = sl = 0 rl = 0 ∧ sl > 0 sl > rl > 0 rl > 0 ∧ rl = sl α[l] = 1 – rl = 0 rl > 0 rl − sl > 0 α[l] = 2 – – sl = 0 sl = 0 α[l] = 3 – – – rl = sl = 0 Let α ∈ U k be the global state of the counters in a configuration (p, σx$, c). Consider a transition T = (p, σx$, c) ⇒ (q, x$, c0 ) and its associated finite se- quence of increments/decrements {di }, di ∈ {−1, 0, 1}k . We say that T is stable w.r.t. α if {di } is stable w.r.t. α (i.e. the global state of the counters in (q, x$, c0 ) is still α), whereas T changes α into β, with α ≺ β, if {di } changes α into β α α (i.e. the global state of the counters in (q, x$, c0 ) is β). We write ⇒β (resp., ⇒α ) for a transition that changes α into β (resp., that is stable). The transitive closure α α of ⇒β is ⇒? β . The global state of the counters is used to define suitable subsets of the set of states Q of a 1-reversal k-counter machine. Indeed, for any β ∈ U k we define the set of states Qβ as follows. Definition 6 (Qβ ). Let (k, Q, Σ, $, δ, q0 , F ) ∈ DFCM(k, 0, 1). Then, Qβ ⊆ Q is inductively deter- mined as follows: (β = 0k ) Q0k is the set of states in Q that are reachable from q0 by a sequence of transitions that are stable w.r.t. 0k , 0k Q0k = {q ∈ Q|∃w ∈ Σ ? : (q0 , wx$, 0)⇒? k (q, x$, 0)}; 0 α 0 k (β 6= 0 ) Let Qβ = {q ∈ Q|∃p ∈ Qα , σ ∈ Σ : α ≺ β, ∧(p, σx$, c)⇒ β (q, x$, c0 )}. Then, Qβ = Q0β ∪ Q00β where β Q00β = {q ∈ Q|∃w ∈ Σ ? , p ∈ Q0β : (p, wx$, c)⇒?(q, x$, c0 ). β Example 1. Figure 1 shows a machine M in DFCM6 (2, 0, 1). A label of type σ1 , σ2 , b1 b2 /d1 d2 , D indicates a transition on an input symbol in {σ1 , σ2 } and two counters c1 , c2 satisfying κ(c1 ) = b1 and κ(c2 ) = b2 (in Fig. 1 the symbol d stands for any symbol in {0, 1}). D represents the movement of the input head, and d1 , d2 the increments/decrements. The only sets of states Qα that are not empty are Q00 = Q01 = {q̇}, Q11 = {q̇, t, u}, Q22 = {u}, Q23 = Q32 = {u, v} and Q33 = {q̈, u, v, z}. a,dd/01,R b,11/−1−1,R b,d1/10,S b,11/10,R b,11/00,R . q s t u /0 0,R b,01/00,R 0 a,dd/10,S b,0 b,10/00,R a,dd/00,R .. $,00/00,R a,b,00/00,R q z v d,dd/00,R Fig. 1. A machine M in DFCM6 (2, 0, 1). In the next section we define a DFA M 0 whose states are distinguished copies of states in Qα , for any α ∈ U k with Qα 6= ∅. The automaton M 0 has transitions from a state p in Qα to a state q that belongs to Qα or to Qβ , with α ≺ β. 3 The s-automaton Let M = (k, Q, Σ, $, δ, q̇, {q̈}) ∈ DFCM6 (k, 0, 1) and consider a triple (α, p, σ), with α ∈ U k , p ∈ Qα and σ ∈ Σ. An evolution of (α, p, σ) is a sequence {(pi , αi , di )}i=1...r such that: – di ∈ {−1, 0, 1}k , αi ∈ U k , 1 ≤ i ≤ r; – pi ∈ Qαi ; – α ≺ α1 and αj ≺ αj+1 for all j with 1 ≤ j < r; – for all j, with 1 ≤ j ≤ r, {di }i=1...j changes α to αj ; – δ(p, σ, ν(α)) = (p1 , S, d1 ), δ(pi , σ, ν(αi )) = (pi+1 , S, di+1 ) for 1 ≤ i < r − 1, and δ(pr−1 , σ, ν(αr−1 )) = (pr , R, dr ). We denote by Ev(α, p, σ) the set of all possible evolutions of a given triple (α, p, σ). Notice that this set is finite and can be computed in time O(3k|Q|). If α is the global state of the counters in a configuration (p, σx$, c) of M , then it is immediate that a one-symbol transition (p, σx$, c) ⇒ (q, x$, c0 ) uniquely identifies an evolution {(pi , αi , di )}i=1...r in Ev(α, p, σ) such that αr is the global 0 0 state Pr of the counters in the configuration (q, x$, c ) and c = c + d, where d = i=1 di . Our aim is that of defining a suitable DFA M 0 that uses weighted symbols to simulate a machine M ∈ DFCM6 (k, 0, 1). The automaton M 0 (equipped with a suitable set of linear constraints and a morphism) is used to specify a language L in RCM such that L = L(M ), see Sect. 4. In the counter machine M , a one-symbol transition on σ ∈ Σ may act differ- ently on different counters, so the alphabet of M 0 is a suitable alphabet Σ 0 6= Σ that takes into account increments/decrements. So, consider a triple (α, p, σ), with p ∈ Qα , and let Ev(α, p, σ) contain an evolution E = {(pi , αi , di )}i=1...r , with αr [l] = 3 if and only if α[l] = 3. Notice thatPin E no new counter is 0 set to zero. In this case, a symbol σd (with d = i di ) is added to Σ to 0 simulate E. Furthermore, if Ev(α, p, σ) contains an evolution E where the l counters in G = {i1 , ie , . . . , il } change state from a value lesser than 3 to 3 (i.e. α[ij ] < αr [ij ] = 3 and d[ij ] < 0 for 1 ≤ j ≤ l), then Σ 0 should contain a symbol σdG . Such a symbol is called guess-symbol as it is used by M 0 to guess that a one-symbol transition of M resets some counters. The weight of a symbol σdG (resp., σd ) is W (σdG ) = d (resp., W (σd ) = d ). All the previous remarks lead to a particular DFA which is called the s-automaton associated with M . Definition 7 (s-automaton). Let M = (k, Q, Σ, $, δ, q̇, {q̈}) be a counter ma- chine in DFCM6 (k, 0, 1). The s-automaton associated with M is the deterministic finite state automaton M 0 = (Q0 , Σ 0 , δ 0 , q̇0k , F 0 ) where: – Q0 = {qα |α ∈ U k , q ∈ Qα }, G(i) – Σ 0 = {σi , σi | σ ∈ Σ, i ∈ [−c|Q|, c|Q|]k , c = 3k + 1, G(i) ⊆ {l | i[l] < 0}}, ? – F 0 = {qα | α ∈ {0, 3}k , Qα 6= ∅, (q, $, 0k ) → (q̈, $, 0k ) in M }, and δ 0 : Q0 × Σ 0 7→ Q0 is defined as follows. Let (α, p,Pσ) be a triple of M that r admits an evolution E = {pi , αi , di }i=1,...,r , with d = i=1 di . If for all l such 0 that αr [l] = 3 one has α[l] = 3, then set δ (pα , σd ) = qαr , where q = pr . Otherwise, let G = {j | d[j] < 0 ∧ α[j] < αr [j] = 3} (G 6= ∅ since in E the global state of at least one counter changes from e to 3, with e < 3) and set δ 0 (pα , σdG ) = qαr . a 01 a 01 a 02 a 01 b 20 q00 q01 t11 q11 b 20 {1} b −1−1 a 00 a 00 b −1−1 a 00 b00 b00 b −1−1 u32 a 00 u 23 u 22 u11 v33 {2} b−1−1 {1,2} b 00 b00 b −1−1 a 00 a 00 b00 b00 z 33 v32 v23 u33 a 00 a 00 a 00 b 00 b00 Fig. 2. The s-automaton M 0 . Example 2. Figure 2 shows the s-automaton M 0 associated with the counter machine M of Fig. 1. The initial state is q00 . A word w accepted by M 0 either belongs to Σ00?k = {σ0k | σ ∈ Σ}? or it contains at least one symbol σd or σdG with d[l] < 0 for at least one l. In particular, for any l with 1 ≤ l ≤ k, the word w contains at most one symbol σdG with l ∈ G. In other words, M 0 can guess only once that a particular counter drops to 0. The next section shows how to construct a suitable system of linear constraints to impose that each guess on a set of counters G is made in the right place, i.e. when M (during a one-symbol transition) actually resets all the counters in G. 4 LDFCM6 and RCM In this section we compare RCM to LDFCM6 . We recall that RCM is not contained in LDFCM [3, Thm. 9], whereas it is contained in LNFCM [3, Thm. 10]. In order to prove that LDFCM6 ( RCM it is sufficient to show that for any L ∈ LDFCM6 there exist a regular language R, a set C of linear constraints and a morphism µ (injective on R ∩ [C]) such that L = hR, C, µi. Theorem 1. LDFCM6 ( RCM. Proof. Since LDFCM6 ⊆ LDFCM , by [3, Thm. 9] one has LDFCM6 6= RCM. So, let M = (k, Q, Σ, $, δ, q̇, {q̈}) be a counter machine in DFCM6 (k, 0, 1), and let M 0 = (Q0 , Σ 0 , δ 0 , q̇0k , F 0 }) be the s-automaton associated with M (see Def. 7). We construct a system C of linear constraints such that L(M ) = hL(M 0 ), C, µi, where µ : Σ 0? 7→ Σ ? is an injective morphism on L(M 0 ) ∩ [C] defined by µ(σd ) = µ(σdG ) = σ. Recall that symbols σd , σdG in Σ 0 have weight W (σd ) = W (σdG ) = d. Weights are used to define the system C. Indeed, M 0 has been defined so that it reads a symbol σd (or σdG ) if and only if M adds d to the counters when it reads σ = 0 µ(σd ) = µ(σdG ). Hence, the weight Pn of a word wP in L(M 0 ) consisting P of n symbols, w = σ1 σ2 · · · σn , is W (w ) = j=1 W (σj ) = σG ∈Σ 0 i|w0 |σiG + σi ∈Σ 0 i|w0 |σi . 0 0 0 0 0 0 i As observed at the end of Sect. 3, a word w0 ∈ L(M 0 ) either belongs to Σ00?k , or, for all l with 1 ≤ l ≤ k, it has at most one occurrence of a symbol σdG such that l V ∈ G. Thus, we consider the system C of linear constraints given by C0 ∨ (Ck+1 1≤l≤k Cl ), where X X C0 : |w|σiG = 0 ∧ |w|σi = 0, i i6=0k XX Cl : |w|σiG ≤ 1, i l∈G   ^ X X Ck+1 :  i[l]|w|σiG + i[l]|w|σi = 0 . 1≤l≤k σiG ∈Σ 0 σi ∈Σ 0 The constraint C0 is satisfied only by words in Σ00?k , whereas Cl is satisfied only by words with at most one guess-symbol associated with the l-th counter. Lastly, Ck+1 is satisfied by words of weight 0k . Now, we prove that µ is injective on L(M 0 ) ∩ [C]. Suppose that there exist x1 , x2 ∈ L(M 0 ) ∩ [C] such that x1 = xτ1 z1 and x2 = xτ2 z2 , with x, z1 , z2 ∈ Σ 0? , τ1 , τ2 ∈ Σ 0 , τ1 6= τ2 , µ(τ1 ) = µ(τ2 ) = σ and z = µ(z1 ) = µ(z2 ). Let y = µ(x). Since M is deterministic, there is only one pair (p, c), with p ∈ Q and |y| c ∈ Nk , such that (q̇, yσz$, 0k ) ⇒ (p, σz$, c). Furthermore, also the transition s = (p, σz$, c) ⇒ (p̂, z$, c + i) is uniquely determined, as well as i ∈ Zk . By construction, τ1 6= τ2 implies τ1 = σi and τ2 = σiG , for a suitable set G of indices such that i[l] < 0 for all l ∈ G. Thus, the automaton M 0 reads x and enters a suitable state pα . Then the two computations have different evolutions: 1. M 0 reads τ1 = σi and enters p̂β , with β[l] = 2 for all l such that i[l] < 0; 2. M 0 reads τ2 = σiG and enters p̂γ , with γ[l] = 3 for all l ∈ G (hence γ 6= β). Consider Case (2). Once in p̂γ , if M 0 has a transition on a symbol of weight j then the condition j[l] = 0 necessarily holds for all l ∈ G. This implies W (z2 )[l] = 0 for all l ∈ G. If W (x)[l] 6= −i[l] for an integer l ∈ G, then Ck+1 is not satisfied and x2 6∈ L(M 0 ) ∩ [C]. So, one has W (x)[l] = −i[l] for all l ∈ G, that is, W (xτ2 )[l] = 0. Now, consider Case (1). Once in p̂β , in all the following transitions (i.e. on reading z1 ) M 0 can read only symbols τ with W (τ )[l] ≤ 0 for all l ∈ G. Furthermore, in order to enter a final state q̈α (with α[l] = 3 for all l ∈ G), M 0 has to read a guess symbol τ (in z1 ) such that W (τ )[l] < 0 for at least one l in G. This implies W (z1 )[l] < 0. Lastly, by recalling that W (xτ2 )[l] = W (xτ1 )[l] = 0, it follows that W (x1 )[l] < 0, hence x1 does not satisfy C and x1 6∈ L(M 0 ) ∩ [C]. Next, we proceed to prove L(M ) = µ(L(M 0 ) ∩ [C]). (L(M ) ⊆ µ(L(M 0 ) ∩ [C])) Let w ∈ L(M ). If w is accepted without incre- menting any counter then consider the word w̃ obtained from w by replacing a symbol σ with σ0k , that is, w̃ ∈ Σ00?k and µ(w̃) = w. By Def. 7, it is immediate that the automaton M 0 on input w̃ enters the final state q̈0k , hence w̃ ∈ L(M 0 ). Moreover, one has w̃ ∈ [C0 ], hence w̃ ∈ [C]. Otherwise, let G ⊆ {1, 2 . . . , k} be the set of counters that are increased (at least once) by M during the computation which accepts w = σ1 · · · σn (recall that M accepts a word with all counters equal to 0). For each l ∈ G, let il = e if the one-symbol transition consuming σe changes the global state of the l-th counter to 3, that is, e−1 (q̇, w$, 0k ) ⇒ (p, σe · · · σn $, c) ⇒ (p̂, σe+1 · · · σn $, c + i) with c[l] + i[l] = 0. Possibly, one has il = im for l 6= m. This means that, for a suitable r with 1 ≤ r ≤ |G|, the set G is uniquely partitioned into r disjoint sets G1 , . . . , Gr by the equivalence relation l ≡ m if and only if il = im . So, each set Gj uniquely identifies a symbol σr(j) such that the r(j)-th one- symbol transition (the one that reads σr(j) ) sets all the counters in Gj to zero, that is, (pr(j) , σr(j) · · · σn $, cr(j) ) ⇒ (pr(j)+1 , σr(j)+1 · · · σn $, cr(j) + ir(j) ) with cr(j) [d] + ir(j) [d] = 0 for all d ∈ Gj . Now, consider the word w0 ∈ Σ 0? that is obtained by replacing in w the Gj symbols σr(j) with σir(j) , and by replacing all the remaining symbols σe with σie (ie is the effect on the counters when M reads σe ). By recalling the relation between one-symbol transitions and evolutions (see Sect. 3), it directly follows from Def. 7 that w0 ∈ L(M 0 ). Moreover, one has also w0 ∈ [C]. Indeed, w0 6∈ [C0 ], whereas for all l one has w0 ∈ [Cl ] (only one guess for each counter l) and w0 ∈ [Ck+1 ] (one has W (w0 ) = 0 since w0 is constructed so that M 0 guesses the value of each counter in the right place, i.e. when M actually resets the counter). (µ(L(M 0 ) ∩ [C]) ⊆ L(M )) Let w0 ∈ L(M 0 ) ∩ [C] and w = µ(w0 ). If w0 ∈ Σ00?k |w| then, by Def. 7, in M there exists a suitable p ∈ Q such that (q̇, w$, 0k ) ⇒ ∗ (p, $, 0k ) → (q̈, $, 0k ), that is, w ∈ L(M ). Otherwise, w0 can be uniquely written as w = x1 σiG11 x2 σiG22 · · · xr σiGrr xr+1 , with xj ∈ {σi |σ ∈ Σ, i ∈ [−3k|Q|, 3k|Q|]k }? , 0 Sr 0 j=1 G Tj ⊆ {1, . . . , k} and Gp ∩ Gq = ∅ for p 6= q. Notice that w 6∈ [C0 ], hence w0 ∈ 1≤l≤k+1 [Cl ]. This means that for each j, with 1 ≤ j ≤ r, and for all G f ∈ Gj one has W (x1 σiG11 · · · xj σij j )[f ] = 0 and W (x1 σiG11 · · · xj )[f ] > 0, that is, ij [f ] = −W (x1 σiG11 · · · xj )[f ]. Furthermore, for all states pα entered by M 0 on G j+1 reading xj+1 σij+1 · · · xr σiGrr xr+1 one has α[l] = 3 for all l ∈ Gj . In other words, G if σi (or σiG ) is a symbol occurring in w0 to the right of σij j , then the condition 0 i[l] = 0 necessarily holds for all l ∈ Gj . RemarkSrthat M enters a final state q̈β k for a suitable β ∈ {0, 3} with β[l] = 3 for l ∈ j=1 Gj . So, it is sufficient to prove that for any h with 1 ≤ h ≤ |w0 |, if in M 0 one h has (q̇0k , w0 ) ⇒ (pβ , w>h 0 ) then in M there exists a sequence of h transitions 0k 0 (q̇, w$, 0k )⇒h(p, w>h $, c) with c = W (w≤h ). Indeed, w0 ∈ L(M 0 ) ∩ [C] implies β that M 0 accepts w0 by entering a final state q̈β , with β ∈ {0, 3}k and W (w0 ) = 0k : then M enters q̈ with all counters equal to zero (i.e. c = 0k ), hence w ∈ L(M ). We reason by induction on h. (h = 1). The first symbol of w0 is a symbol σi , for suitable σ ∈ Σ and i ∈ Nk . So, by Def. 7, if δ 0 (q̇0k , σi ) = qβ then in MP one has that Ev(0k , q̇, σ) contains the evolution {(pi , αi , di )}i=1,...,r , with i = i di , pr = q and αr = β, that is, 0k (q̇, σw>1 $, 0k )⇒(q, w>1 $, i), with W (w≤1 ) = W (σi ) = i. β h−1 (h > 1). By induction hypothesis, one has (q̇0k , w0 ) ⇒ (pβ , w≥h 0 ) (in M 0 ) 0k 0 and (q̇, w$, 0k )⇒h−1(p, w≥h $, c) (in M ), with c = W (w 0, whereas it eventually has a transition on a guess-symbol σdG with d[l] < 0 (in order to enter a final state qη with η[l] = 3). Thus, one has c0 [j] ≥ 0 for all j, and in M there exists the sequence 0k β of h transitions (q̇, w$, 0k )⇒h−1(p, σw>h $, c)⇒ γ (q, w>h $, c0 ), with c0 = W (w≤h ). β 0 Furthermore, one has κ(c ) = ν(γ). Indeed, γ[l] = 0 implies β[l] = 0 and i[l] = 0, hence c0 [l] = 0 and κ(c0 )[l] = ν(γ)[l] = 0. Otherwise, if γ[l] = 1 then either i[l] > 0 (hence c0 [l] > 0 and κ(c0 )[l] = ν(γ)[l] = 1), or i[l] = 0, β[l] = 1, c0 [l] = c[l] > 0 and κ(c0 )[l] = ν(γ)[l] = 1. Recall that γ[l] = 3 only if β[l] = 3 (hence i[l] = 0, c0 [l] = c[l] = 0 and κ(c0 )[l] = ν(γ)[l] = 0). Lastly, consider the case γ[l] = 2. If i[l] = 0 then one necessarily has β[l] = 2 and c0 [l] = c[l] > 0, hence κ(c0 )[l] = ν(γ)[l] = 1. Otherwise, if i[l] < 0 then one has W (w≤h )[l] > 0 (as shown above) and c[l] > c0 [l] > 0, hence κ(c0 )[l] = ν(γ)[l] = 1. We proceed similarly if the h-th symbol of w0 is a guess symbol σiG . The only 0 0 difference is that for l ∈ G one has W (wh one has G W (σi )[l] = i[l] = 0 (resp., W (σj )[l] = j[l] = 0). t u As an immediate consequence of the previous theorem one has: Corollary 1. Let L ∈ LDFCM6 . Then, the generating function φL (x) is holo- nomic. Corollary 1 implies that a language L is not in LDFCM6 if its generating function i i2 is not holonomic. For instance, the language L =P{a b } isn neither in LDFCM6 nor in RCM since its generating function φL (x) = n≥0 an x 6= 0 is not holonomic (here, an = |{w ∈ L | |w| = n}|). Indeed, for any holonomic function f (x) = n P n≥0 bn x that is not a polynomial, there exists a constant m such that for any i ≥ 0 at least one of the coefficients in the sequence bi , bi+1 , . . . , bi+m is not zero (see [12]). It is immediate that such a property does not hold for {an }. 5 Conclusions and further work We have shown that LDFCM6 ( RCM. This is a new result concerning the re- lationship between RCM and other classes of languages defined by means of reversal bounded counter machines. In particular, we are close to solve the con- jecture LDFCM ( RCM stated in [3], since we think that the technique used to deal with multiple counters should work also in the case of negative cycles. We stress that proving this conjecture would lead to an important result con- cerning the holonomicity of the generating functions of languages in LDFCM . As far as we know, apart [11, Cor.1 and Cor.2], there is not a general result regard- ing the generating functions of languages accepted by suitable classes of reversal bounded counter machines. This makes the previous conjecture of particular interest. References 1. A. Bertoni, P. Massazza, and N. Sabadini. Holonomic generating functions and context free languages. Int. J. Found. Comput. Sci., 3(2):181–191, 1992. 2. M.l Cadilhac, A. Finkel, and P. McKenzie. Affine parikh automata. RAIRO-Theor. Inf. Appl., 46(4):511–545, 2012. 3. G. Castiglione and P. Massazza. On a class of languages with holonomic generating functions. Theor. Comput. Sci., 658:74–84, 2017. 4. N. Chomsky and M. P. Schützenberger. The algebraic theory of context-free lan- guages. Computer Programming and Formal Systems, pages 118–161, 1963. 5. P. Flajolet. Ambiguity and transcendence. In ICALP1985, Proc., volume 194 of Lect. Notes Comput. Sc., pages 179–188. Springer, 1985. 6. P. Flajolet. Analytic models and ambiguity of context-free languages. Theor. Comput. Sci., 49:283–309, 1987. 7. O.H. Ibarra. Reversal-bounded multicounter machines and their decision problems. J. ACM, 25(1):116–133, January 1978. 8. F. Klaedtke and H. Rueß. Parikh automata and monadic second-order logics with linear cardinality constraints. Technical report, Dep. of Computer Science, Univ. of Freiburg, 2002. 9. F. Klaedtke and H. Rueß. Monadic second-order logics with cardinalities. In ICALP2003, Proc., volume 2719 of Lect. Notes Comput. Sc., pages 681–696. Springer, 2003. 10. P. Massazza. Holonomic functions and their relation to linearly constrained lan- guages. RAIRO-Theor. Inf. Appl., 27(2):149–161, 1993. 11. P. Massazza. On the conjecture Ldfcm(1,0,1) ( RCM. In CIAA 2017, Proc., volume 10329 of Lect. Notes Comput. Sc., pages 175–187. Springer, 2017. 12. R.P. Stanley. Differentiably finite power series. Eur. J. Combin., 1(2):175 – 188, 1980. 13. D. Zeilberger. A holonomic systems approach to special functions identities. J. Comput. Appl. Math., 32(3):321 – 368, 1990.