Rational index of context-free languages in exp (^ pn) and n^(( n)^1/p)

There are many ways to measure the complexity of languages. Rational index, introduced by \textit{L. Boasson} and \textit{M. Nivat} [C. R. Acad. Sci., Paris, Sér. A 284, 559-562, 625-628, 703-705 (1977; Zbl 0359.68095, Zbl 0359.68096, Zbl 0354.68107)], is one of them and behaves well when combined with rational transductions: if \(L\geq L'\) (i.e., there exists a rational transduction \(\tau\) such that \(\tau(L)=L')\), then the rational index \(\rho_ L\) of L provides an upper bound on \(\rho_{L'}\) since \[ \exists c\in {\mathbb{N}}^*\quad \forall n\in {\mathbb{N}}^*: cn(\rho_ L(cn)+1)\geq \rho_{L'}(n). \] Thus we define the family \underbar{Pol} of languages whose rational indexes grow less than polynomial, and the family \(\overline{Exp}\) of languages whose rational indexes grow more than exponential functions. It was conjectured by \textit{L. Boasson, B. Courcelle} and \textit{M. Nivat} [SIAM J. Comput. 10, 284-296 (1981; Zbl 0469.68083)], that all context- free languages belong to \underbar{Pol} or \(\overline{Exp}\). The aim of this paper is to show context-free languages whose rational indexes are exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta ((\ln n)^{1/p})}\) proving thereby that this conjecture is false. The results and most of the proofs appearing in this paper are those of the authors' thesis (Univ. Paris VI, 1981).

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104111)