We prove that the generating function of a language accepted by a one-way deterministic one-reversal counter machine without negative 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 properties, namely it contains only some particular languages with holonomic generating function.
A well-known result of Chomsky-Schutzenberger [
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
homogeneous linear di erential equation with polynomial coe cients (see [
In this paper we prove that the conjecture is true for the subclass LDFCM6
consisting of the languages accepted by deterministic one-reversal counter
machines without negative cycles (informally, on reading a symbol the automaton
can decrement a counter by a value bounded by a constant). The result is
obtained by generalizing the technique used in [
In this section we give some basics about languages, classes of languages and automata of our interest in the paper. Let = f 1; 2; : : : ; hg be a nite alphabet and w 2 ?. For all 2 we indicate by jwj the number of occurrences of in w. The length of w is jwj = P 2 jwj . The pre x of w consisting of the rst h symbols is w h. Similarly, w>h is the su x of w starting at h + 1. Given two nite alphabets and , a morphism : ? 7! ? is said to be length preserving if for all w 2 ? one has j (w)j = jwj. In particular, we are interested in length preserving morphisms that are injective on a xed 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! f0; 1gk de ned 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 2 Nk, then c + d is the their sum (componentwise).
Linear constraints on the number of occurrences of symbols in an
alphabet have been used in [
De nition 1 (linear constraint). A linear constraint on the occurrences of symbols of = f 1; 2; : : : ; hg in w 2 ? is an expression of the form h X cijwj i 4 ch+1; i=1
with ci 2 Z; 4 2 f<; ; =; 6=; ; >g:
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 [
De nition 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 [
In Section 4, the class RCM will be compared to the class of languages
accepted by a particular family of counter machines. We recall that a two-way
k-counter machine is a nite automaton equipped with k counters. The
operations 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 [
A con guration of M is a triple (q; x$; c) where q 2 Q, x 2 is the unread su x of the input word, and the content of the k counters is c 2 Nk. The transition relation on the set of con gurations is denoted by !, and its re exive and transitive closure by !. Hence, we write (p; v; c) ! (q; z; c0) if and only if (p; ; (c)) = (q; b), c0 = 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. De nition 4 ()). Let M = (k; Q; ; $; ; q_; F ) 2 DFCM(k; 0; 1). For any x 2 ? and 2 we write (p; x$; c) ) (q; x$; c0) if and only if p; q 2 Q, and either (p; ; (c)) = (q; R; d) with c0 = c + d, or (p; ; (c)) = (q1; S; d1), (q1; ; (c + d1)) = (q2; S; d2); : : : ; (qh; S; (c + Pi=1::h di)) = (q; R; dh+1), with c0 = c + Pi=1::h+1 di.
Notice that the transition (p; x$; c) ) (q; x$; c0) uniquely identi es a sequence fdig of tuples in f 1; 0; 1gk and a sequence fqig of states in Q. A sequence of jwj one-symbol transitions reading a word w is shortened as (p; wx$; c) j)wj (q; x$; c0). A word w 2 ? is accepted by M if and only if (q_; w$; 0k) j)wj (p; $; c) ! (q; $; c0), for some q 2 F and suitable c; c0 2 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 nal state, denoted by q, and that a word is accepted with all the counters equal to 0. The only accepting con guration 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).
De nition 5 (negative cycle). Let M = (k; Q; ; $; ; q_; fqg) be a counter machine in DFCM(k; 0; 1). Then, M has a negative cycle if there exists a sequence of states q1; : : : ; qh 2 Q, a symbol 2 and a suitable b 2 f0; 1gk such that: { (q1; ; b) = (q2; S; d1); (q2; ; b) = (q3; S; d2); : : : ; (qh; ; b) = (q1; S; dh) { d[l] < 0 for at least one l, with 1 l k, where d = Pi=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 2 DFCM6 (k; 0; 1), the e ect on the counters of any one-symbol transition is bounded. More precisely, the following lemma holds. Lemma 1. Let (k; Q; ; $; ; q_; fqg) 2 DFCM6 (k; 0; 1). Then, for any one-symbol transition (p; x$; c) ) (q; x$; c + d) one has 0 jd[l]j (3k + 1)jQj for all l, with 1 l k.
In particular, a counter machine that always terminates can not have a positive cycle (de ned as in Def. 5, with the only di erence 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 machine, each counter is exactly in one of four di erent states, denoted by a value in the set U = f0; 1; 2; 3g 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, nally, 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 de ned as follows: given ; 2 U k, de ne 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 2 ?, then one has 0 1 r, with 0 = 0k (and r 2 f3; 0gk if w is accepted). Since the machine is reversal, there are at most 3k + 1 di erent 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! f0; 1gk be the morphism de ned by (0) = (3) = 0 and (1) = (2) = 1. If is the global state of the counters in a given con guration (q; x$; c), then one has ( ) = (c).
A sequence fdig of tuples in f 1; 0; 1gk 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, fdig is compatible with 2 U k if it is 1-reversal acceptable and for all l, with 1 l k, one has: { if [l] = 3 then 8i di[l] = 0; { if [l] = 2 then 8i di[l] 0; { if [l] = 0 then jfijdi[l] = 1gj
jfijdi[l] = 1gj.
Furthermore, given ; 2 U k with b, we say that a sequence fdig, 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 = jfijdi[l] = 1gj, sl = jfijdi[l] = 1gj). A sequence fdig 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 2 U k be the global state of the counters in a con guration (p; x$; c). Consider a transition T = (p; x$; c) ) (q; x$; c0) and its associated nite sequence of increments/decrements fdig, di 2 f 1; 0; 1gk. We say that T is stable w.r.t. if fdig 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 fdig 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 de ne suitable subsets of the set of states Q of a 1-reversal k-counter machine. Indeed, for any 2 U k we de ne the set of states Q as follows.
Let (k; Q; ; $; ; q0; F ) 2 DFCM(k; 0; 1). Then, Q Q is inductively determined 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, Example 1. Figure 1 shows a machine M in DFCM6 (2; 0; 1). A label of type 1; 2; b1b2=d1d2; D indicates a transition on an input symbol in f 1; 2g and two counters c1, c2 satisfying (c1) = b1 and (c2) = b2 (in Fig. 1 the symbol d stands for any symbol in f0; 1g). 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 = fq_g, Q11 = fq_; t; ug, Q22 = fug, Q23 = Q32 = fu; vg and Q33 = fq; u; v; zg.
a,dd/01,R . q b,d1/10,S b,11/10,R
b,11/00,R s Let M = (k; Q; ; $; ; q_; fqg) 2 DFCM6 (k; 0; 1) and consider a triple ( ; p; ), with 2 U k, p 2 Q and 2 . An evolution of ( ; p; ) is a sequence f(pi; i; di)gi=1:::r such that: { di 2 f 1; 0; 1gk, i 2 U k, 1 i r; { pi 2 Q i ; { 1 and j j+1 for all j with 1 j < r; { for all j, with 1 j r, fdigi=1:::j changes to j ; { (p; ; ( )) = (p1; S; d1), (pi; ; ( i)) = (pi+1; S; di+1) for 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 nite and can be computed in time O(3kjQj). If is the global state of the counters in a con guration (p; x$; c) of M , then it is immediate that a one-symbol transition (p; x$; c) ) (q; x$; c0) uniquely identi es an evolution f(pi; i; di)gi=1:::r in Ev( ; p; ) such that r is the global state of the counters in the con guration (q; x$; c0) and c0 = c + d, where d = Pr i=1 di.
Our aim is that of de ning a suitable DFA M 0 that uses weighted symbols to simulate a machine M 2 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 2 may act di erently on di erent 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 2 Q , and let Ev( ; p; ) contain an evolution E = f(pi; i; di)gi=1:::r, with r[l] = 3 if and only if [l] = 3. Notice that in E no new counter is set to zero. In this case, a symbol d (with d = Pi di) is added to 0 to simulate E. Furthermore, if Ev( ; p; ) contains an evolution E0 where the l counters in G = fi1; ie; : : : ; ilg 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 G. Such a symbol is called guess-symbol as it is used by M 0 to guess that a onde-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 . De nition 7 (s-automaton). Let M = (k; Q; ; $; ; q_; fqg) be a counter machine in DFCM6 (k; 0; 1). The s-automaton associated with M is the deterministic nite state automaton M 0 = (Q0; 0; 0; q_0k ; F 0) where: { F 0 = fq j { Q0 = fq j {
2 U k; q 2 Q g, 0 = f i; iG(i) j 2 ; i 2 [ cjQj; cjQj]k; c = 3k + 1; G(i) 2 f0; 3gk; Q 6= ;; (q; $; 0k) !? (q; $; 0k) in M g, fl j i[l] < 0gg, and 0 : Q0 0 7! Q0 is de ned as follows. Let ( ; p; ) be a triple of M that admits an evolution E = fpi; i; digi=1;:::;r, with d = Pr i=1 di. If for all l such that r[l] = 3 one has [l] = 3, then set 0(p ; d) = q r , where q = pr. Otherwise, let G = fj j d[j] < 0 ^ [j] < r[j] = 3g (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 .
q00 a00 u32 v32 Fig. 2. The s-automaton M 0.
a 00 b00 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 = f 0k j 2 g? or it contains aatnylelaswtitohne1symlbolk, dthoer wodGrdwiwthcodn[lt]a<ins0aftormaotstleoanste osnymebl.oIln pdGarwtiicthulalr2, fGor. 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 su cient to show that for any L 2 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. where : 0? 7!
( dG) = . lPertooMf. =Sin(cke; QL;DFC;M$;6 ; q_; fLqDgF)CMbe, bayco[3u,ntTehrmm.a9ch]ionneeinhaDsFLCDMFC6M(k6; 06=; 1R),CaMnd. Sleot, M 0 = (Q0; 0; 0; q_0k ; F 0g) 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, ? is an injective morphism on L(M 0) \ [C] de ned by ( d) = C0 :
Cl : Ck+1 : 1 1 l k jwj iG
G i 2 0 jwj iG = 0 ^
X jwj i = 0; i6=0k 1;
Recall that symbols d; dG in 0 have weight W ( d) = W ( dG) = d. Weights are used to de ne the system C. Indeed, M 0 has been de ned so that it reads a symbol d (or dG) if and only if M adds d to the counters when it reads = ( d) = ( dG). Hence, the weight of a word w0 in L(M 0) consisting of n symbols, w0 = 10 20 n0, is W (w0) = Pjn=1 W ( j0) = P iG2 0 ijw0j iG + P i2 0 ijw0j i .
As observed at the end of Sect. 3, a word w0 2 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 2 G. Thus, we consider the system C of linear constraints given by C0 _ (Ck+1 V1 l k Cl), where The constraint C0 is satis ed only by words in 00?k , whereas Cl is satis ed only by words with at most one guess-symbol associated with the l-th counter. Lastly, Ck+1 is satis ed by words of weight 0k.
Now, we prove that is injective on L(M 0) \ [C]. Suppose that there exist x1; x2 2 L(M 0) \ [C] such that x1 = x 1z1 and x2 = x 2z2, with x; z1; z2 2 0?, 1; 2 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 2 Q and y c 2 Nk, such that (q_; y z$; 0k) )jj (p; z$; c). Furthermore, also the transition s = (p; z$; c) ) (p^; z$; c + i) is uniquely determined, as well as i 2 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 2 G. Thus, the automaton M 0 reads x and enters a suitable state p . Then the two computations have di erent 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 2 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 2 G. This implies W (z2)[l] = 0 for all l 2 G. If W (x)[l] 6= i[l] for an integer l 2 G, then Ck+1 is not satis ed and x2 62 L(M 0) \ [C]. So, one has W (x)[l] = i[l] for all l 2 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 2 G. Furthermore, in order to enter a nal state q (with [l] = 3 for all l 2 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 62 L(M 0) \ [C].
Next, we proceed to prove L(M ) = (L(M 0) \ [C]).
(L(M ) (L(M 0) \ [C])) Let w 2 L(M ). If w is accepted without incrementing any counter then consider the word w~ obtained from w by replacing a symbol with 0k , that is, w~ 2 00?k and (w~) = w. By Def. 7, it is immediate that the automaton M 0 on input w~ enters the nal state q0k , hence w~ 2 L(M 0). Moreover, one has w~ 2 [C0], hence w~ 2 [C].
Otherwise, let G f1; 2 : : : ; kg 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 2 G, let il = e if the one-symbol transition consuming e changes the global state of the l-th counter to 3, that is, (q_; w$; 0k) e)1 (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 jGj, 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 identi es a symbol r(j) such that the r(j)-th onesymbol 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 2 Gj.
Now, consider the word w0 2 0? that is obtained by replacing in w the symbols r(j) with iGrj(j) , and by replacing all the remaining symbols e with ie (ie is the e ect 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 2 L(M 0). Moreover, one has also w0 2 [C]. Indeed, w0 62 [C0], whereas for all l one has w0 2 [Cl] (only one guess for each counter l) and w0 2 [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 2 L(M 0) \ [C] and w = (w0). If w0 2 00?k then, by Def. 7, in M there exists a suitable p 2 Q such that (q_; w$; 0k) j)wj (p; $; 0k) ! G(q1;x$2; 0ik2), that is, w 2 L(M ). Otherwise, w0 can be uniquely written as w0 = x1 i1 G2 xr iGrr xr+1, with xj 2 f ij 2 ; i 2 [ 3kjQj; 3kjQj]kg?, Sjr=1 Gj f1; : : : ; kg and Gp \ Gq = ; for p 6= q. Notice that w0 62 [C0], hence w0 2 T1 l k+1[Cl]. This means that for each j, with 1 j r, and for all f 2 Gj one has W (x1 iG11 xj iGjj )[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 reading xj+1 iGj+j+11 xr iGrr xr+1 one has [l] = 3 for all l 2 Gj. In other words, if i (or iG) is a symbol occurring in w0 to the right of iGjj , then the condition i[l] = 0 necessarily holds for all l 2 Gj. Remark that M 0 enters a nal state q for a suitable 2 f0; 3gk with [l] = 3 for l 2 Sjr=1 Gj.
So, it is su cient to prove that for any h with 1 h jw0j, if in M 0 one has (q_0k ; w0) )h (p ; w>0h) then in M there exists a sequence of h transitions k (q_; w$; 0k))0h(p; w>h$; c) with c = W (w0 h). Indeed, w0 2 L(M 0) \ [C] implies that M 0 accepts w0 by entering a nal state q , with 2 f0; 3gk and W (w0) = 0k: then M enters q with all counters equal to zero (i.e. c = 0k), hence w 2 L(M ).
We reason by induction on h.
(h = 1). The rst symbol of w0 is a symbol i, for suitable 2 and i 2 Nk. So, by Def. 7, if 0(q_0k ; i) = q then in M one has that Ev(0k; q_; ) contains the evolution f(pi; i; di)gi=1;:::;r, with i = Pi di, pr = q and r = , that is, k (q_; w>1$; 0k)0)(q; w>1$; i), with W (w 1) = W ( i) = i.
(h > 1). By induction hypothesis, one has (q_0k ; w0) h)1 (p ; w0 h) (in M 0) k and (q_; w$; 0k))0 h 1(p; w h$; c) (in M ), with c = W (w<0h) and (c) = ( ).
Suppose that the h-th symbol of w0 is i. By Def. 7, if 0(p ; i) = q then in M one has that Ev( ; p; ) contains the evolution f(pi; i; di)gi=1;:::;r, with i = Pi di, pr = q, r = and [l] < 3 if [l] < 3. Let c0 = c + i and consider an index l such that i[l] < 0 (hence [l] = 2). Since W (w0 h) = c + i, if W (w0 h)[l] 0 then W (w0)[l] < 0 holds and w0 62 L(M 0) \ [C]. Indeed, once in q (and in all subsequent states) the automaton M 0 has not a transition on a symbol of weight e with e[l] > 0, whereas it eventually has a transition on a guess-symbol dG with d[l] < 0 (in order to enter a nal state q with [l] = 3). Thus, one has c0[j] 0 for all j, and in M there exists the sequence k of h transitions (q_; w$; 0k))0 h 1(p; w>h$; c))(q; w>h$; c0), with c0 = W (w h). Furthermore, one has (c0) = ( ). 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 di erence is that for l 2 G one has W (w<0h)[l] = i[l], hence W (w0 h)[l] = 0 and c[l] + i[l] = c0[l] = 0. Indeed, if W (w0 h)[l] 6= 0 then W (w0)[l] 6= 0, since by Def. 7 one has [l] = 3 and for any symbol i (resp., jG) in w>0h one has W ( i)[l] = i[l] = 0 (resp., W ( jG)[l] = j[l] = 0). tu As an immediate consequence of the previous theorem one has: Corollary 1. Let L 2 LDFCM6 . Then, the generating function L(x) is holonomic.
Corollary 1 implies that a language L is not in LDFCM6 if its generating function
is not holonomic. For instance, the language L = faibi2 g is neither in LDFCM6 nor
in RCM since its generating function L(x) = Pn 0 anxn 6= 0 is not holonomic
(here, an = jfw 2 L j jwj = ngj). Indeed, for any holonomic function f (x) =
Pn 0 bnxn that is not a polynomial, there exists a constant m such that for any
i 0 at least one of the coe cients in the sequence bi; bi+1; : : : ; bi+m is not zero
(see [
We have shown that LDFCM6 ( RCM. This is a new result concerning the
relationship between RCM and other classes of languages de ned by means of
reversal bounded counter machines. In particular, we are close to solve the
conjecture LDFCM ( RCM stated in [
We stress that proving this conjecture would lead to an important result concerning 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 regarding the generating functions of languages accepted by suitable classes of reversal bounded counter machines. This makes the previous conjecture of particular interest.