=Paper=
{{Paper
|id=Vol-2243/paper18
|storemode=property
|title=On the Generating Functions of Languages Accepted by Deterministic One-reversal Counter
Machines
|pdfUrl=https://ceur-ws.org/Vol-2243/paper18.pdf
|volume=Vol-2243
|authors=Paolo Massazza
|dblpUrl=https://dblp.org/rec/conf/ictcs/Massazza18
}}
==On the Generating Functions of Languages Accepted by Deterministic One-reversal Counter
Machines==
https://ceur-ws.org/Vol-2243/paper18.pdf
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.