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

DOI10.1016/0304-3975(88)90038-2zbMath0646.68091OpenAlexW1967175417MaRDI QIDQ1104111

Jean-Marc Farinone, Laurent Pierre

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90038-2

zbMATH Keywords

context-free languagescomplexity of languagesrational indexes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (2)

Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $ ⋮ Rational indexes of generators of the cone of context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Rational Index: A Complexity Measure for Languages

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})}\)