Rational transductions and

complexity of counting problems^{∗}^{†}

Christian Choffrut

Université Paris VII, Laboratoire d’Informatique Théorique et de Programmation, UA248, Tour 55-56, 2 Place Jussieu,75221 Paris Cedex 05, France

Massimiliano Goldwurm

Università degli Studi di Milano, Dipartimento di Scienze dell’Informazione, via Comelico 39, 20135 Milano, Italy

Please send any correspondence about the paper to the following address :

Massimiliano Goldwurm

Dip. Scienze dell’Informazione

Università degli Studi di Milano

via Comelico 39

20135 Milano, Italy

(Tel: +39.2.55006305;

email: goldwurm@imiucca.csi.unimi.it, or goldwurm@hermes.mc.dsi.unimi.it)

∗A preliminary version of this work was accepted for presentation at the 17th Symposium on Mathematical Foundations of Computer Science (MFCS ’92), Prag August 24-28, 1992.

†This research was supported by ESPRIT Working Group ASMICS (CEC contract n.3166), PRC Mathématiques et Informatique, MURST Project 40% “Algoritmi, modelli di calcolo e strutture informative”.

Abstract

This work presents an algebraic method based on rational transductions to study the sequential and parallel complexity of counting problems for regular and context-free languages. This approach allows to obtain old and new results on the complexity of ranking and unranking as well as on other problems concerning the number of prefixes, suffixes, subwords and factors of a word which belongs to a fixed language. Other results concern a suboptimal compression of finitely ambiguous context-free languages, the complexity of the value problem for rational and algebraic formal series in noncommuting variables and a characterization of regular and Z-algebraic languages by means of ranking functions.

1 Introduction

Several counting problems defined on formal languages have recently been studied in the literature. We recall the problem of counting the accepting computations in various kinds of nondeterministic machine models [21, 3, 22], the problem of computing the number of words of given length in a language [7] and the classical ranking problem [13, 15, 17]. These problems are related to several topics of computational complexity and provide examples of complete functions for interesting complexity classes. Given a language L ⊆ Σ^{∗}, the ranking problem for L consists of computing for an input x ∈ Σ^{∗} the number of words in L which either have length less than the length of x or, having the same length, precede x lexicographically. The problem is clearly related to determining a succinct and efficiently computable representation of the words of a language and in fact it has been studied as a special case of optimal compression [13]. The ranking problem for any language in P belongs to the class ♯P of functions computing the number of accepting computations of nondeterministic Turing machines working in polynomial time [21]. The problem turns out to be ♯P −complete for several simple classes of languages included in P and in particular for finitely ambiguous context-free languages [17]. However, the problem is NC^{1}−reducible to integer division in the case of regular languages [6, 18], it belongs to ♯SAC^{1} ⊆ NC^{2} for unambiguous context-free languages and, more generally, for languages accepted by 1-way Unambiguous Auxiliary PDA [17, 22].

In this work we study the parallel and sequential complexity of ranking and other counting problems in the ”easy” case, assuming the log-space uniform families of bounded fan-in Boolean circuits as model of parallel computation [9]. We refer the reader to [9] and [22] for the definition of the classes NC^{k} and ♯SAC^{k}, respectively. Concerning the sequential complexity, we consider the RAM model under the logarithmic cost criterion [1]. In this model any arithmetic operation over two n-bit integers, can be executed in O(n) time and space, provided that their addresses in the memory of the RAM are polynomially bounded. This amounts to neglecting a factor of log n log log n bit operations when evaluating the time required by product and division. We also observe that all our sequential algorithms execute arithmetic operations over integers of O(n) bits, n being the size of the input.

We present an algebraic method based on rational transductions to study the sequential and parallel complexity of ranking and other counting problems in case of regular and context-free languages. This approach allows to reduce these problems to computing the coefficients of rational and algebraic formal series in noncommuting variables. Intuitively, in order to determine complexity bounds for computing a function f : Σ^{∗} → N, we view it as a formal power series in N⟨⟨X⟩⟩ (f(x) is the coefficient of the power series associated with the word x). It just happens, in all our examples, that this power series is the image of an algebraic (resp. rational) formal power series g ∈ N⟨⟨X⟩⟩ by a suitable faithful rational transduction τ : X^{∗} → N⟨⟨X⟩⟩ (under reasonable conditions rational transductions extend to formal series). Since algebraic (resp. rational) formal power series are preserved by rational transductions, f is itself an algebraic (resp. rational) formal power series. In other words, computing f(w) for an arbitrary word x reduces to computing the coefficient associated with x in the series.

For this reason we first study the value problem for formal series r ∈ N⟨⟨Σ⟩⟩ which is the problem of computing the coefficient (r, x) for a given string x ∈ Σ^{∗}. Interpreting the results in [22], it turns out that the value problem for any algebraic formal series r ∈ N⟨⟨Σ⟩⟩ belongs to ♯SAC^{1} and hence lies in NC^{2}. Moreover, the problem can be solved in O(n^{4}) time and O(n^{3}) space on RAM under logarithmic cost criterion and, if r is bounded, the time and space bounds can be reduced to O(n^{2} log n) and O(n^{2}), respectively. For rational formal series in N⟨⟨Σ⟩⟩ the value problem can be solved by a RAM with the logarithmic cost, in O(n^{2}) time and O(n) space. Furthermore, it can be solved by (log-space) uniform families of bounded fan-in Boolean circuits of O(log n log log n) depth and polynomial size.

As an application of these considerations to languages, for any L ⊆ Σ^{∗}, we consider the following functions :

1) rank_{L}(x) = ♯{y ∈ L : y ≤_{r} x}, 2) shrank_{L}(x) = ♯{y ∈ L : |y| = |x|, y ≤_{lex} x},

3) pref_{L}(x) = ♯{y ∈ L : y is a prefix of x},

4) suf_{L}(x) = ♯{y ∈ L : y is a suffix of x},

5) fac_{L}(x) = ♯{(w, z) : x = wyz, y ∈ L, y ≠ ϵ, w, z ∈ Σ^{∗}},

6) sub_{L}(x) = ♯{(z_{0}, z_{1}, …, z_{n}) : z_{i} ∈ Σ^{∗}, x = z_{0}y_{1}z_{1} ⋯ y_{n}z_{n}, y_{i} ∈ Σ, and y_{1}y_{2} ⋯ y_{n} ∈ L}.

Here ♯S denotes the cardinality of a set S; ≤_{lex} is the lexicographic order over Σ^{∗}; ≤_{r} is the rank order over Σ^{∗}, that is y ≤_{r} x if and only if |y| < |x|, or (|y| = |x|, y ≤_{lex} x). Note that fac_{L}(x) is the number of occurrences of factors of x belonging to L while sub_{L}(x) is the number of occurrences of subwords of x belonging to L.

We show that for every unambiguous context-free language L ⊆ Σ^{∗}, the functions rank_{L}, shrank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L} are algebraic formal series and hence they belong to ♯SAC^{1} ⊆ NC^{2} and can be computed in O(n^{4}) time and O(n^{3}) space on a RAM under logarithmic cost criterion. This also implies that the ranking problem for any unambiguous context-free language, having a bounded number of words of length k for any k ∈ N, can be solved in O(n^{2} log n) sequential time and O(n^{2}) space. The same results hold if L is unambiguous Z-algebraic, that is if its characteristic function is a solution of a system of algebraic equations with coefficients in Z. Analogously, we prove that for any regular language L the functions rank_{L}, shrank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L} are rational formal series. Hence they can be computed in O(n^{2}) time and O(n) space or in depth O(log n log log n) and polynomial size by (log-space) uniform families of boolean circuits of bounded fan-in. We also extend the previous analysis by showing that a language L is regular if and only if rank_{L} is rational if and only if shrank_{L} is rational. A similar result is proved for unambiguous Z-algebraic languages.

Another application of our method concerns the compression of finitely ambiguous context-free languages. We recall that an optimal compression of a language L ⊆ Σ^{∗} is a partial function f : Σ^{∗} → {0, 1}^{∗}, which is defined and one-one on L, such that |f(x)| ≤ ⌈log_{2} c_{L}(|x|)⌉ for all but finitely many x ∈ L, where c_{L} denotes the census function of L, i.e. c_{L} : N → N such that c_{L}(n) = ♯{x ∈ L : |x| ≤ n}. A partial function g : Σ^{∗} → {0, 1}^{∗} is said to be an optimal compression of L up to a constant factor if g is defined and one-one on L and, for every x ∈ L, |g(x)| ≤ k|f(x)| where k ∈ N and f is an optimal compression of L. Clearly rank_{L} is an optimal compression of L and, in case it is not efficiently computable, a natural problem is to find suboptimal compressions for L which admit efficient algorithms. This is the case of finitely ambiguous context-free languages since some of them have ♯P -complete ranking function [17]. For an arbitrary finitely ambiguous context-free grammar G, we consider the function weakrank_{G} : Σ^{∗} → N which maps each x ∈ Σ^{∗} to the number of leftmost derivations of words y ∈ Σ^{∗} such that y ≤_{r} x. It has already been observed that such a function is an optimal compression of L(G) up to a constant factor and that it is computable in polynomial time [13, Sec 5.2]. We improve this result by showing that weakrank_{G} is an algebraic formal series for every context-free (cycle-free) grammar G and hence it is computable in ♯SAC^{1} and admits sequential algorithms working in O(n^{4}) time and O(n^{3}) space. Again, these bounds can be reduced to O(n^{2} log n) and O(n^{2}) respectively, if L has a bounded number of words of length k for any k ∈ N.

The last application concerns the complexity of the unranking problem for regular and unambiguous context-free languages. Intuitively this is the problem of computing the inverse of rank_{L} for a given language L. Such a problem is clearly related to uncompressing strings [13] and it has been considered in connection with the analysis of the p-effective entropy of languages [18]. A natural formal definition of the unranking problem can be given as follows. For any language L, let unrank_{L} : {1}^{∗} × N → L be the partial function such that, for every n, m ∈ N, unrank_{L}(1^{n}, m) = x if and only if |x| = n and shrank_{L}(x) = m, and it is undefined otherwise. Refining some results of [18], we show that unrank_{L} is computable respectively in O(n^{2}) time and O(n) if L is regular, in O(n^{5}) time and O(n^{3}) space if L is unambiguous context-free, and in O(n^{3} log n) time and O(n^{2}) space if, in addition, L has a bounded number of words of given length.

2 Formal series and the value problem

Let Σ be a finite alphabet, Σ^{∗} the free monoid it generates and ϵ the empty word, i.e., the unit of the monoid. Given a commutative semiring ⟨R, +, ·⟩, a formal series in the noncommuting variables σ ∈ Σ over the semiring R, is a mapping r : Σ^{∗} → R. For every x ∈ Σ^{∗} the value r(x) is also denoted by (r, x) and is called the coefficient of r at x. Following the usual convention, we represent r as a formal sum r = ∑_{x∈Σ^{∗}}(r, x)x. The class of all formal series r is denoted by R⟨⟨Σ⟩⟩. An element r ∈ R⟨⟨Σ⟩⟩ is called quasiregular if and only if (r, ϵ) = 0, where ϵ denotes the empty word. Moreover, a formal series r ∈ N⟨⟨Σ⟩⟩ is said to be bounded if there exists an integer k ∈ N such that (r, x) ≤ k for every x ∈ Σ^{∗}. The standard operations of sum and Cauchy product on formal series induce a semiring structure on R⟨⟨Σ⟩⟩ [19, p. 12], [5, p. 3].

Rational and algebraic formal power series are defined in numerous textbooks [5, 11, 19]. For our purpose we take a maybe unusual approach based on so-called weighted grammars (cf., e.g. [20]).

Let us first briefly recall the standard notions on context-free grammars. A contextfree grammar is a quadruple ⟨V, Σ, P, S⟩, where V is the set of variables, Σ is the set of terminal symbols, P ⊆ V ×(Σ∪V)^{∗} is the finite family of productions and S ∈ V is the initial symbol. A production in P is written as A → w, where A ∈ V and w ∈ (Σ∪V)^{∗}. The relation of one-step derivation on (Σ ∪ V)^{∗} is denoted by ⇒. Its transitive (resp. transitive and reflexive) closure is denoted by ⇒^{+} (resp. ⇒^{∗}). A context-free grammar G = ⟨V, Σ, P, S⟩ is said to be cycle- free if every A ∈ V cannot be derived from itself in G, i.e. A ⇒^{+} A does not hold in G. We recall that in such a grammar the number of derivations of x from A is finite for every x ∈ Σ^{∗} and every A ∈ V. A contextfree grammar G = ⟨V, Σ, P, S⟩ is said to be weighted if G is cycle-free, P does not contain any ϵ-production, i.e., if P ∩ V × {ϵ} = ∅, and there is a function p : P → R associating with each production β ∈ P its weight p(β). Such a grammar generates a quasiregular formal series r_{G} ∈ R⟨⟨Σ⟩⟩ in the following way. The weight of a derivation A = x_{0} ⇒ x_{1} ⇒ … ⇒ x_{n} in G is defined as the product p(β_{1})p(β_{2}) … p(β_{n}), where each β_{i} ∈ P is the production yielding the one-step derivation x_{i−1} ⇒ x_{i}. Then, for every x ∈ Σ^{∗}, the coefficient (r_{G}, x) is defined as the sum of the weights of all leftmost derivations of x from S.

Now let r ∈ R⟨⟨Σ⟩⟩ be given by r = c + s, where c ∈ N and s ∈ R^{alg}⟨⟨Σ⟩⟩ is quasiregular. Then r is algebraic (resp. rational) if s is the formal series generated by a weighted context-free (resp. regular) grammar [20]. We denote by R^{alg}⟨⟨Σ⟩⟩ and R^{rat}⟨⟨Σ⟩⟩ respectively the set of algebraic and rational formal series in R⟨⟨Σ⟩⟩. It is well known that rational (resp. algebraic) power series are subsemirings of the semiring of all power series R⟨⟨Σ⟩⟩.

For every language L ⊆ Σ^{∗}, we denote by χ_{L} the characteristic series of L in N⟨⟨Σ⟩⟩:

(χ_{L}, x) = \{ \begin{matrix}1 & if x ∈ L \\ 0 & otherwise \end{matrix}

We recall that L is regular (resp. unambiguous context-free) if and only if χ_{L} is rational (resp. algebraic).

The value problem for a formal series r ∈ N⟨⟨Σ⟩⟩ is defined as the problem of computing, for an input x ∈ Σ^{∗}, the coefficient (r, x). In the case of rational power series we have

Proposition 1 The value problem for any rational formal series r ∈ N^{rat}⟨⟨Σ⟩⟩ is solvable by (log-space) uniform families of bounded fan-in Boolean circuits of polynomial size and O(log n log log n) depth. Moreover the problem can be solved in O(n^{2}) time and O(n) space on a RAM under logarithmic cost criterion.

Proof. It is known that r is rational if and only if there are two arrays π, η ∈ N^{k} and a monoid morphism μ : Σ^{∗} → N^{k×k} such that (r, x) = πμ(x)η^{T} for every x ∈ Σ^{∗} [5]. This means that the value problem for r is equivalent to computing the product of n = |x| square matrices of bounded size with entries in N each of which has a bounded number of bits. Using the Chinese Remainder Theorem such a computation can be executed in depth O(log n log log n) and polynomial size by a log-space uniform boolean circuits of bounded fan-in [7, Lemma 2.8]. Since the coefficient (r, x) is a O(n)-bit integer, it is also clear that this computation works in quadratic time and linear space on the present RAM model.

We now turn to the case of algebraic power series.

Proposition 2 The value problem for any algebraic formal series r ∈ N^{alg}⟨⟨Σ⟩⟩ belongs to the class ♯SAC^{1} and hence lies in NC^{2}. It can be solved in O(n^{3}) space and O(n^{4}) time by a RAM under logarithmic cost criterion. Moreover, sequential time and space can be reduced to O(n^{2} log n) and O(n^{2}) respectively, if r is bounded.

Proof. Given r ∈ N^{alg}⟨⟨Σ⟩⟩, let G = ⟨V, Σ, P, S⟩ be a weighted context-free grammar in Greibach normal form which generates r, the existence of which is established by [19, Theorem IV.2.3]. It is known that G can be simulated by a pushdown automaton A so that for every string x ∈ Σ^{∗} there is a one-one correspondence between the set of leftmost derivations of x in G and the set of accepting computations of A on input x [19]. Such a simulation can be modified so that the automaton A, before executing the steps corresponding to a production β in G, nondeterministically chooses an integer k such that 1 ≤ k ≤ p(β), where p : P → N is the weight function of G. This amounts to associating with each production of the grammar as many as p(β) ϵ- moves which only modify the current state of A. Then, for every x ∈ Σ^{∗}, the value of (r, x) equals the number of accepting computations of A on input x. Since the problem of computing the number of accepting computations in pushdown automata belongs to ♯SAC^{1} [22], the same holds for the value problem of algebraic formal series in N^{alg}⟨⟨Σ⟩⟩.

Now, let us consider the sequential case. It is known that every r ∈ N^{alg}⟨⟨Σ⟩⟩ can be generated by a weighted context-free grammar G = ⟨V, Σ, P, S⟩ in Chomsky normal form [19, Theorem IV.2.2]. This fact allows to apply the classical CKY algorithm for context-free recognition [14]. Given an input x = x_{1}x_{2} … x_{n} ∈ Σ^{∗}, this algorithm computes an upper triangular matrix [t_{ij}] of size (n + 1) × (n + 1) such that t_{ij} ⊆ V for every i, j and, if i < j, then A ∈ t_{ij} if and only if A ⇒^{+} x_{i+1} … x_{j}. The algorithm can be modified by defining, for every A ∈ V, a formal series Â ∈ N⟨⟨Σ⟩⟩ such that, for each y ∈ Σ^{∗}, (Â, y) is the sum of the weights of all leftmost derivations of y from A. Then, denoting by w_{ij} the string x_{i+1} ⋯ x_{j} for every 0 ≤ i < j ≤ n, the coefficients (Â, w_{ij}) can be computed from (Â, w_{i,i+1}) = p(A → x_{i+1}), by using the following equations

(Â, w_{ij}) = ∑_{(A→BC)∈P} p(A → BC) ∑_{i<k<j}(B̂, w_{ik})(Ĉ, w_{kj}), 0 ≤ i < i + 1 < j ≤ n.

Clearly (r_{G}, x) = (Ŝ, w_{0n}) has O(n) bits, and hence it is easy to see that this algorithm works in O(n^{4}) time and O(n^{3}) space on RAM.

Similar modifications can be applied to solve the value problem in case of bounded algebraic series. In fact the membership problem for finitely ambiguous context-free languages can be tested in O(n^{2}) time using Earley’s algorithm [10]. The detailed description of this algorithm can be found in [2, Sec.4.2.2] and [14, Sec.12.6]. Here we only recall the key idea of the modified version. Let G = ⟨V, Σ, S, P ⟩ be a context-free grammar. Given an input x = x_{1}x_{2} … x_{n} ∈ Σ^{∗}, Earley’s algorithm builds up a table of lists T_{ik}, where 0 ≤ i ≤ n and 0 ≤ k ≤ i, each of which contains dotted productions of the form [A → α · β] such that (A → αβ) is a production of the grammar. The term [A → α·β] belongs to list T_{ik} if and only if there are γ, δ ∈ (V ∪Σ)^{∗} such that S ⇒^{∗} γAδ, γ ⇒^{∗} x_{1} … x_{k} and α ⇒^{∗} x_{k+1} … x_{i}. Clearly x is generated by G if and only if a term [S → α·] lies in list T_{n0}. Now, assuming that G is a weighted context-free grammar, the modified version of the algorithm manipulates terms of the form [A → α · β, a], where [A → α · β] is defined as before and a is the sum of the weights of all leftmost derivations α ⇒^{∗} x_{k+1} … x_{i}. The value (r_{G}, x) is obtained as the sum of all products a × p(S → α) where the term [S → α·, a] belongs to list T_{n0}. Assuming the grammar is finitely ambiguous, each list has a finite number of terms, and the value a in each term [A → α · β, a] is bounded by a constant. Hence the table of lists can be kept by a RAM in O(n^{2}) space even under logarithmic cost criterion. Moreover, the time cost of each arithmetic operation is bounded by O(log n), which is the time needed to determine the location of a list T_{ik} in the memory of our RAM model. This amounts to increase the overall time complexity by a factor O(log n) with respect to the original version.

3 Faithful rational transductions

In this section we discuss some properties of faithful rational transductions and show their relationship with regulated representations.

Given two alphabets X and Y, a representation is a monoid morphism μ : X^{∗} → R^{rat}⟨⟨Y ⟩⟩^{m×m}. Since R^{rat}⟨⟨Y ⟩⟩ is a subsemiring of R⟨⟨Y ⟩⟩, R^{rat}⟨⟨Y ⟩⟩^{m×m} is a monoid with respect to the matrix product induced by the operations in R^{rat}⟨⟨Y ⟩⟩. The representation μ is said to be regulated if, for some k ∈ N, μ(x)_{ij} is quasiregular for every i, j = 1, …, m and every x ∈ X^{∗} of length greater than k.

As a consequence, any regulated representation μ : X^{∗} → R^{rat}⟨⟨Y ⟩⟩^{m×m} can be extended to formal series. Indeed, for every r ∈ R⟨⟨X⟩⟩ the matrix μ(r) = ∑_{x∈X^{∗}}(r, x)μ(x) is well-defined

μ(r)_{ij} = ∑_{y∈Y^{∗}}( ∑_{x∈X^{∗}}(r, x)(μ(x)_{ij}, y))y

since in the inner sum, all coefficients (μ(x)_{ij}, y) are equal to zero except maybe if |x| ≤ k|y|. In the particular case when r is the characteristic series of a language L ⊆ X^{∗}, i.e., r = χ_{L}, note that the following holds for every y ∈ Y^{∗}

(μ(χ_{L})_{ij}, y) = ∑_{x∈L}(μ(x)_{ij}, y)

The proof of the following proposition can be found in [19, Lemma II.11.5, IV.7.1]. Proposition 3 If R is a commutative semiring and μ : X^{∗} → R^{rat}⟨⟨Y ⟩⟩^{m×m} is a regulated representation then we have:

1) Each entry of μ(r) is rational for every r ∈ R^{rat}⟨⟨X⟩⟩;

2) Each entry of μ(r) is algebraic for every r ∈ R^{alg}⟨⟨X⟩⟩.

A function τ : X^{∗} → R^{rat}⟨⟨Y ⟩⟩ is a rational transduction if there is a representation μ : X^{∗} → R^{rat}⟨⟨Y ⟩⟩^{m×m} such that τ(x) = μ(x)_{1m}, for every x ∈ X^{+}. We say that μ realizes τ; observe that, since τ(ϵ) does not depend on μ, infinitely many rational transductions can be realized by a given representation. Also, τ is said to be faithful if the set {x ∈ X^{∗} : (τ(x), y) ≠ 0} is finite for every y ∈ Y^{∗} [4, p. 87]. The properties of faithfulness and regulatedness are linked by the following proposition.

Proposition 4 Let τ : X^{∗} → N^{rat}⟨⟨Y ⟩⟩ be a rational transduction. Then τ is faithful if and only if there exists a regulated representation μ : X^{∗} → N^{rat}⟨⟨Y ⟩⟩^{m×m} that realizes it.

Proof. Without loss of generality we may assume that τ(ϵ) = 0. Let μ : X^{∗} → N^{rat}⟨⟨Y ⟩⟩^{m×m} be a representation realizing τ. This representation can be chosen to be trim. In other words we may assume that for every i = 1, …, m there are x, y ∈ X^{∗} such that μ(x)_{1i} ≠ 0 and μ(y)_{im} ≠ 0 [4, Prop. III.7.4]. Suppose that μ is not a regulated representation. Then there are two indices i, j ∈ {1, …, m} such that (μ(w)_{ij}, ϵ) ≠ 0 for infinitely many w ∈ X^{∗}. Since μ is trim there exist x, y ∈ X^{∗}, z, t ∈ Y^{∗},such that (μ(x)_{1i}, z) ≠ 0 and (μ(y)_{jm}, t) ≠ 0. Then for infinitely many w ∈ X^{∗} we have (μ(xwy)_{1m}, zt) ≠ 0 proving that τ is not faithful. On the other hand, assume μ is a regulated representation. Then there exists k ∈ N such that for every string x of length greater than or equal to k and every pair of indices i, j, (μ(x)_{ij}, ϵ) = 0. As a consequence, for every x ∈ X^{∗}, if |x| ≥ λk with λ ≥ 0, and (μ(x)_{ij}, y) ≠ 0, then |y| ≥ λ. It follows that the set {x ∈ X^{∗} : (μ(x)_{ij}, y) ≠ 0} is finite for every y ∈ Y^{∗} and every pair of indices i, j proving that τ is faithful.

We close this section with a useful notation. A rational transduction τ : X^{∗} → N^{rat}⟨⟨Y ⟩⟩ is unambiguous if (τ(x), y) ≤ 1 for all x ∈ X^{∗}, y ∈ Y^{∗}. Such a transduction may be identified with a function from X^{∗} into P (Y^{∗}). With this convention, if τ is an unambiguous faithful rational transduction, then for every L ⊆ X^{∗} the image by τ of the characteristic series χ_{L} can be rewritten as

τ(χ_{L}) = ∑_{y∈Y^{∗}} ♯(L ∩ τ^{−1}(y))y  (1)

4 Rational and algebraic counting functions

In this section we apply the general properties presented in the previous section to the counting functions defined in Section 1. In the following proofs we denote by σ_{1}, σ_{2}, …, σ_{k} the elements of the alphabet Σ, lexicographically ordered by σ_{1} < σ_{2} < … < σ_{k}.

Proposition 5 Given a finite alphabet Σ and a language L ⊆ Σ^{∗}, let us denote by f_{L} any of the functions rank_{L}, shrank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L}. Then, there exists a faithful rational transduction τ : Σ^{∗} → N^{rat}⟨⟨Σ⟩⟩ such that f_{L} = τ(χ_{L}) for every language L ⊆ Σ^{∗}.

Proof. Let μ be the regulated representation defined by

μ(σ_{i}) = [ \begin{matrix}σ_{i} & ∑_{j>i} σ_{j} & ∑_{j≠i} σ_{j} & ∑_{j≥i} σ_{j} + χ_{Σ}χ_{Σ^{+}} \\ 0 & χ_{Σ} & 0 & χ_{Σ} \\ 0 & 0 & χ_{Σ} & χ_{Σ}χ_{Σ^{+}} \\ 0 & 0 & 0 & 0 \end{matrix} ] , for 1 ≤ i ≤ k,

with the convention that the sum over an empty set of indices is equal to 0. It is easy to check that for every x ∈ Σ^{+}

μ(x) = [ \begin{matrix}x & ∑_{|y|=|x|,x<_{r}y} y & ∑_{|y|=|x|,x≠y} y & ∑_{x≤_{r}y} y \\ 0 & χ_{Σ^{|x|}} & 0 & χ_{Σ^{|x|}} \\ 0 & 0 & χ_{Σ^{|x|}} & χ_{Σ^{|x|}}χ_{Σ^{+}} \\ 0 & 0 & 0 & 0 \end{matrix} ]

This means that μ realizes the unambiguous rational transduction τ defined by τ(x) = {y ∈ Σ^{∗} : x ≤_{r} y} for every x ∈ Σ^{+}, and τ(ϵ) = Σ^{∗}. Then, for every L ⊆ Σ^{∗}, via Equation (1) we obtain

τ(χ_{L}) = ∑_{y∈Σ^{∗}} ♯(L ∩ τ^{−1}(y))y = rank_{L}

Hence the proposition is proved for f_{L} = rank_{L}.

The same reasoning holds for the functions shrank_{L}, pref_{L}, suf_{L}, replacing μ respectively by the regulated representations μ_{1}, μ_{2}, μ_{3} defined as follows:

μ_{1}(σ_{i}) = [ \begin{matrix}σ_{i} & ∑_{j>i} σ_{j} & ∑_{j≥i} σ_{j} \\ 0 & χ_{Σ} & χ_{Σ} \\ 0 & 0 & 0 \end{matrix} ] , μ_{2}(σ_{i}) = [ \begin{matrix}σ_{i} & σ_{i}χ_{Σ^{∗}} \\ 0 & 0 \end{matrix} ] , μ_{3}(σ_{i}) = [ \begin{matrix}0 & χ_{Σ^{∗}}σ_{i} \\ 0 & σ_{i} \end{matrix} ] ,

where 1 ≤ i ≤ k. Consider the faithful rational transductions τ_{1}, τ_{2}, τ_{3} realized by μ_{1}, μ_{2}, μ_{3} respectively, such that τ_{1}(ϵ) = 0 and τ_{2}(ϵ) = τ_{3}(ϵ) = χ_{Σ^{∗}}. It is easy to see that τ_{1}, τ_{2}, τ_{3} are unambiguous and satisfy the following relations for every x ∈ Σ^{+} : τ_{1}(x) = {y ∈ Σ^{|x|} : x ≤_{lex} y}, τ_{2}(x) = {y ∈ Σ^{∗} : xz = y, z ∈ Σ^{∗}}, τ_{3}(x) = {y ∈ Σ^{∗} : zx = y, z ∈ Σ^{∗}}, Now, let μ_{4} be the regulated representation defined by

μ_{4}(σ_{i}) = [ \begin{matrix}0 & χ_{Σ^{∗}}σ_{i} & χ_{Σ^{∗}}σ_{i}χ_{Σ^{∗}} \\ 0 & σ_{i} & σ_{i}χ_{Σ^{∗}} \\ 0 & 0 & 0 \end{matrix} ] , 1 ≤ i ≤ k.

Then, μ_{4} realizes a faithful rational transduction τ_{4} such that τ_{4}(ϵ) = 0 and τ_{4}(x) = χ_{Σ^{∗}}xχ_{Σ^{∗}} = ∑_{y∈Σ^{∗}} ♯{(w, z) : wxz = y, w, z ∈ Σ^{∗}}y for every x ∈ Σ^{+}. Therefore, for every L ⊆ Σ^{∗} and every y ∈ Σ^{∗}, we obtain

(τ_{4}(χ_{L}), y) = ♯{(w, z) : wxz = y, x ∈ L, x ≠ ϵ, w, z ∈ Σ^{∗}} = (fac_{L}, y)

Similarly, consider the faithful rational transduction τ_{5} realized by the representation μ_{5} such that

μ_{5}(σ_{i}) = [ \begin{matrix}0 & χ_{Σ^{∗}}σ_{i}χ_{Σ^{∗}} \\ 0 & σ_{i}χ_{Σ^{∗}} \end{matrix} ] , 1 ≤ i ≤ k,

with τ(ϵ) = 0. In this case we have that sub_{L} = τ_{5}(χ_{L}) for every L ⊆ Σ^{∗}, since τ_{5}(x) = μ_{5}(x)_{12} = χ_{Σ^{∗}}x_{1}χ_{Σ^{∗}}x_{2} ⋯ χ_{Σ^{∗}}x_{n}χ_{Σ^{∗}} for every word x = x_{1}x_{2} ⋯ x_{n} with x_{i} ∈ Σ. Note that both rational transductions τ_{4} and τ_{5} are ambiguous, since e.g., every (τ_{4}(x), y) equals the number of occurrences of x in y.

Applying Proposition 3 to the previous one we obtain the following Theorem 6 Let L ⊆ Σ^{∗} be an unambiguous context-free language. Then the functions shrank_{L}, rank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L} are algebraic formal series in N^{alg}⟨⟨Σ⟩⟩. Moreover, if L is a regular language then the same functions are rational formal series in N^{rat}⟨⟨Σ⟩⟩.

Note that the theorem does not hold if L is inherently ambiguous because in this case χ_{L} is not N-algebraic. However a similar result holds for a larger class of languages.

Theorem 7 Let L ⊆ Σ^{∗} be an unambiguous Z-algebraic language, in the sense that χ_{L} ∈ Z^{alg}⟨⟨Σ⟩⟩. Then the functions shrank_{L}, rank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L} belong to Z^{alg}⟨⟨Σ⟩⟩.

Observe that the class of unambiguous Z-algebraic languages is closed under complement while the class of unambiguous context- free languages is not [16]. In particular there are unambiguous Z-algebraic languages which are not context-free.

These properties allow to establish a characterization of regular and Z-algebraic languages by means of ranking functions. To this end, for every x ∈ Σ^{∗}, let post(x), if any, be the lexicographic minimal string in {y ∈ Σ^{|x|} : x ≤_{lex} y, x ≠ y}, and let prec(x), if any, be the lexicographic maximal string in {y ∈ Σ^{|x|} : y ≤_{lex} x, x ≠ y}. We define the regulated representation μ by

μ(σ_{i}) = [ \begin{matrix}σ_{i} & σ_{i+1} \\ 0 & 0 \end{matrix} ] , for 1 ≤ i ≤ k − 1, and μ(σ_{k}) = [ \begin{matrix}σ_{k} & 0 \\ 0 & σ_{1} \end{matrix} ] .

It is clear that, for every j ∈ N, μ(σ_{k}^{j})_{12} = 0 and, for every x ∈ Σ^{∗} − {σ_{k}^{j} : j ∈ N}, μ(x)_{12} = post(x). Therefore, for every L ⊆ Σ^{∗} we have μ(shrank_{L})_{12} = ∑_{x∈Σ^{∗}}(shrank_{L}, prec(x))x . This implies

χ_{L} = shrank_{L} − μ(shrank_{L})_{12}  (2)

Corollary 8 The following statements are equivalent :

- L ⊆ Σ^{∗} is a regular language;

- shrank_{L} belongs to N^{rat}⟨⟨Σ⟩⟩;

- rank_{L} belongs to N^{rat}⟨⟨Σ⟩⟩.

Proof. By Theorem 6 we only need to prove that both shrank_{L} ∈ N^{rat}⟨⟨Σ⟩⟩ and rank_{L} ∈ N^{rat}⟨⟨Σ⟩⟩ imply L ∈ Rat(Σ^{∗}). Then, by Proposition 3, Equation (2) shows that if shrank_{L} belongs to N^{rat}⟨⟨Σ⟩⟩ then χ_{L} lies in Z^{rat}⟨⟨Σ⟩⟩. Since such a function can only assume values in {0, 1}, it also belongs to N^{rat}⟨⟨Σ⟩⟩ [19, Theorem II.5.2]. A similar reasoning shows that rank_{L} ∈ N^{rat}⟨⟨Σ⟩⟩ implies L ∈ Rat(Σ^{∗}).

The following corollary is proved in the same way.

Corollary 9 For any language L ⊆ Σ^{∗} the following statements are equivalent: - χ_{L} belongs to Z^{alg}⟨⟨Σ⟩⟩;

- shrank_{L} belongs to Z^{alg}⟨⟨Σ⟩⟩;

- rank_{L} belongs to Z^{alg}⟨⟨Σ⟩⟩.

5 Applications to counting problems

Applying Propositions 1, 2 to Theorem 6, we obtain the following complexity bounds.

Theorem 10 Let L ⊆ Σ^{∗} be an unambiguous context-free language. Then the functions shrank_{L}, rank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L} belong to the class ♯SAC^{1} ⊆ NC^{2} and can be computed in O(n^{4}) time and O(n^{3}) space on a RAM under logarithmic cost criterion.

Theorem 11 Let L ⊆ Σ^{∗} be a regular language. Then the functions shrank_{L}, rank_{L}, pref_{L}, suf_{L}, fac_{L}, sub_{L} can be computed in O(n^{2}) time and O(n) space on a RAM under logarithmic cost criterion, or in O(log n log log n) depth and polynomial size by (log-space) uniform boolean circuits of bounded fan-in.

Corollary 12 Let L ⊆ Σ^{∗} be an unambiguous context-free language such that, for some m ∈ N, L contains at most m words of length k for any k ∈ N. Then the functions shrank_{L} and rank_{L} are computable in O(n^{2} log n) time and O(n^{2}) space on a RAM under logarithmic cost criterion.

Proof. From the hypothesis we deduce that shrank_{L} is a bounded algebraic formal series and hence, by Proposition 2, it is computable in O(n^{2} log n) time and O(n^{2}) space. The same result is easily proved for rank_{L} recalling that the census function of L, denoted c_{L}, is computable in quadratic time and linear space under logarithmic cost criterion [12], and observing that rank_{L}(x) = c_{L}(|x| − 1) + shrank_{L}(x) for every x ∈ Σ^{∗}.

A further application of our method concerns the compression of finitely ambiguous context-free languages. To illustrate this point, let G = ⟨V, Σ, P, S⟩ be a weighted context-free grammar and let us define the function weakrank_{G} : Σ^{∗} → N such that weakrank_{G}(x) = ∑_{y≤_{r}x}(r_{G}, y).

Proposition 13 For every weighted context-free grammar G = ⟨V, Σ, P, S⟩, the function weakrank_{G} is an algebraic formal series in N⟨⟨Σ⟩⟩.

Proof. Let us consider the regulated representation μ defined in Proposition 5. It can be proved that, for every weighted context-free grammar G, weakrank_{G} = μ(r_{G})_{13}. Hence the result follows from Proposition 3.

Theorem 14 Every finitely ambiguous context-free language L admits a compression, optimal up to a constant factor, which belongs to ♯SAC^{1} ⊆ NC^{2} and can be computed in O(n^{4}) time and O(n^{3}) space on a RAM under logarithmic cost criterion.

Proof. Let G be a cycle-free context-free grammar of ambiguity k ∈ N that generates L and assign weight 1 to each production in G. Clearly, for every x ∈ Σ^{∗}, weakrank_{G}(x) ≤ k × rank_{L}(x) and hence weakrank_{G} is optimal up to a constant factor. Such a formal series is also algebraic by the previous proposition and hence the result follows from Proposition 2.

The following corollary is proved in the same way.

Corollary 15 Let L ⊆ Σ^{∗} be a finitely ambiguous context-free language such that, for some m ∈ N, L contains at most m words of length k for any k ∈ N. Then a compression of L, optimal up to a constant factor, can be computed in O(n^{2} log n) time and O(n^{2}) space.

Now, let us consider the unranking problem. Our technique can be used to study the problem in case of unambiguous context-free languages.

Proposition 16 For any unambiguous context-free language L ⊆ Σ^{∗}, unrank_{L}(1^{n}, m) can be computed in O(n^{5}) time and O(n^{3}) space on a RAM under logarithmic cost criterion. Moreover, these bounds can be reduced to O(n^{3} log n) and O(n^{2}) respectively, if L is unambiguous context-free and, for some m ∈ N, it contains at most m words of length k for any k ∈ N.

Proof. Let z be a symbol not in Σ and consider the faithful rational transduction τ : Σ^{∗} → N⟨⟨Σ⟩⟩ realized by the representation

μ_{(}σ) = [ \begin{matrix}σ & z \\ 0 & z \end{matrix} ] , σ ∈ Σ,

such that τ(ϵ) = 1. Then let T_{L} be the algebraic formal series given by T_{L} = τ(χ_{L}). Since τ is unambiguous, for every k ∈ N and every x ∈ Σ^{∗}, we have (T_{L}, xz^{k}) = ♯{w ∈ L : |w| = |x| + k, x is a prefix of w}. The value unrank_{L}(1^{n}, m) can be computed by a procedure that first checks whether m ≤ c_{L}(n) − c_{L}(n − 1); then, in the affirmative case, it assigns the values x = ϵ and r = m and executes the following computation :

for i = 1, 2, …, n do

begin

compute the lexicographic minimum element η in Σ such that

r ≤ ∑_{σ≤_{lex}η}(T_{L}, xσz^{n−i})

r = r − ∑_{σ<_{lex}η}(T_{L}, xσz^{n−i})

x = xη end Recalling that c_{L}(n) can be computed in O(n^{2}) time and applying Proposition 2 to

compute the coefficients of T_{L}, we obtain the result.

We conclude by considering the unranking problem for regular languages. To this end, let A = ⟨Q, q_{0}, δ, F ⟩ be a deterministic finite state automaton recognizing a language L ⊆ Σ^{∗} and, for any state q ∈ Q and every n ∈ N, let d_{q}(n) denote the number of words x ∈ Σ^{∗} such that δ(q, x) ∈ F. It is known that each sequence {d_{q}(n)}_{n} satisfies a recurrence equation of the form

c_{0q}d_{q}(n) + c_{1q}d_{q}(n − 1) + ⋯ + c_{kq}d_{q}(n − k) = 0

where k only depends on A and each c_{iq} is a fixed integer [18]. We observe that such recurrences allow to compute d_{q}(n) in O(n^{2}) time and O(n) space; moreover they also allow to compute d_{q}(n − k) from d_{q}(n), d_{q}(n − 1), …, d_{q}(n − k + 1) in linear time for every n > k. Then, applying the binary search technique described in the previous proposition, it can be proved that unrank_{L}(1^{n}, m) is computable in quadratic time and linear space. Hence we obtain the following

Proposition 17 For any regular language L, the function unrank_{L} is computable in O(n^{2}) time and O(n) space on a RAM under logarithmic cost criterion.

References

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading Mass. 1974.

[2] A.V. Aho and J.D. Ullman, The theory of parsing, translation and compiling, Vol. 1, Parsing, Prentice-Hall, Englewood Cliffs, N. J., 1972.

[3] C. Alvarez and B. Jenner, “A very hard log-space counting class”, Theoretical Computer Science 107 (1993), 3-30.

[4] J. Berstel, Transductions and context-free languages, Teubner, Stuttgart, 1979.

[5] J. Berstel and C. Reutenauer, Rational Series and Their Languages, Springer Verlag, Berlin Heidelberg, 1988.

[6] A. Bertoni, D. Bruschi and M. Goldwurm, “Ranking and formal power series”, Theoretical Computer Science 79 (1991) 25-35.

[7] A. Bertoni, M. Goldwurm and N. Sabadini, “The complexity of computing the number of strings of given length in context-free languages”, Theoretical Computer Science 86 (1991), 325-342.

[8] M. Bogni, Algoritmi per il problema del valore di serie formali a variabili non commutative, Degree Thesis in Mathematics, Dip. Scienze dell’Informazione, Università di Milano, June 1991.

[9] S.A. Cook, “A taxonomy of problems with fast parallel algorithms,” Inform. and Control 64 (1985), 2–22.

[10] J. Earley, “An efficient context-free parsing algorithm”, Communications of the ACM 13 n.2 (1970),94-102.

[11] S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974.

[12] P. Flajolet, “Analytic models and ambiguity of context-free languages”, Theoretical Computer Science 49 (1987), 283-309.

[13] A.V. Goldberg and M. Sipser, “Compression and ranking”, SIAM J. Comput. 20 n.3 (1991), 524-536.

[14] M. Harrison, Introduction to formal language theory, Addison-Wesley, Reading Mass., 1978.

[15] L. Hemachandra, “On ranking”, Proc. 2nd Conference on Structure in Complexity Theory (1987), 103-117.

[16] T.N. Hibbard and J. Ullian, “The independence of inherent ambiguity from complementedness among context-free languages”, J. Assoc. Comput. Mach. 13 n.4 (1966), 588-593.

[17] D.T. Huynh, “The complexity of ranking simple languages”, Math. Systems Theory 23 (1990), 1-20.

[18] D.T. Huynh, “Effective entropies and data compression”, Information and Computation 90 (1991),67-85.

[19] A. Salomaa and M. Soittola, Automata theoretic aspects of formal power series, Springer Verlag, Berlin 1978.

[20] D.F. Stanat, “A homomorphism theorem for weighted context-free grammar”, J. Comput. System Sci. 6 (1972), 217-232.

[21] L.G. Valiant, “The complexity of enumeration and reliability problems”, SIAM J. Comput. 8 (1979), 410-420.

[22] V. Vinaj, “Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits”, Proc. 6th Conference on Structure in Complexity Theory (1991), 270-284.