Rational indexes of generators of the cone of context-free languages. (English) Zbl 0745.68068

Summary: The rational index \(\rho_ L\) of a non-empty language \(L\) is a non- decreasing function from \(\mathbb{N} ^*\) into \(\mathbb{N}\), whose asymptotic behavior can be used to classify languages. The rational index behaves well when combined with rational transductions: if a language \(L\) rationally dominates another language \(L'\) (i.e. there exists a rational transduction \(\tau\), such that \(\tau(L)=L'\)), then \(\rho_ L\), the rational index of \(L\), provides an upper bound on \(\rho_{L'}\), since \[ \exists c\in\mathbb{N}^*, \qquad \forall n\in\mathbb{N}^*, \qquad cn(\rho_ L(cn)+1)\geq\rho_{L'}(n). \] Hence all the generators of the rational cone of context-free languages, i.e. the context-free languages which dominate any context-free language, have roughly the same rational indexes, which were known to belong to \(\exp \Omega(n)\cap\exp O(n^ 2)\). This paper improves these bounds. Indeed the rational index of any generator of the rational cone of context-free languages belongs to \(\exp \Theta(n^ 2/\ln n)\).


68Q45 Formal languages and automata
Full Text: DOI


[1] Berstel, J., Transductions and Context-Free Languages (1979), Teubner Verlag · Zbl 0424.68040
[2] Boasson, L.; Nivat, M., Ordres et types de langage, I, II, III, Notes CRAS, 284, 703-705 (1977), série A · Zbl 0354.68107
[3] Boasson, L.; Courcelle, B.; Nivat, M., The rational index, a complexity measure for languages, SIAM J. Comput., 10, 2, 284-296 (1981) · Zbl 0469.68083
[4] Gabarro, J., Index rationnel, centre et langages algébriques, (Thèse de 3ème cycle (1981), Univ. de Paris VI), Rapport L.I.T.P. No. 81-54 · Zbl 0505.68033
[5] Deléage, J.-L.; Pierre, L., The rational index of the Dyck language \(D′^∗1\), Theoret. Comput. Sci., 47, 335-343 (1986) · Zbl 0632.68072
[6] Farinone, J. M., Langages algébriques d’index rationnel singulier, (Thèse de 3ème cycle. Thèse de 3ème cycle, Rapport L.I.T.P, No. 86-64 (1986), Univ. de Paris VII)
[7] Pierre, L.; Farinone, J. M., Rational index of context-free languages in exp \(Θ(np)\) and \(n^Θ(lnnp)\), Theoret. Comput. Sci., 57, 185-204 (1988) · Zbl 0646.68091
[8] Pierre, L.; Farinone, J. M., Context-free languages with rational indexes in \(Θ(n^λ)\) for algebraic numbers λ, RAIRO Inform. Théor. Appl., 24, 3, 275-322 (1990) · Zbl 0701.68068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.