Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\) (Q1104111): Difference between revisions

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).