Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
type: Item
instance of: scholarly article
title: Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
zbMATH Open document ID: 0646.68091
DOI: 10.1016/0304-3975(88)90038-2
author: Laurent Pierre
author: Jean-Marc Farinone
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4055077
zbMATH Keywords: complexity of languages
zbMATH Keywords: context-free languages
zbMATH Keywords: rational indexes
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90038-2
OpenAlex ID: W1967175417
cites work: Q3859267
cites work: Q3686060
cites work: Q4125811
cites work: The Rational Index: A Complexity Measure for Languages
description: scientific article; zbMATH DE number 4055077