Rational indexes of generators of the cone of context-free languages

DOI10.1016/0304-3975(92)90269-LzbMath0745.68068OpenAlexW1987629182MaRDI QIDQ1184983

Laurent Pierre

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90269-l

zbMATH Keywords

rational transductionscomplexity of languagesrational indexcontext- free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

On regular realizability problems for context-free languages ⋮ Rational index of languages with bounded dimension of parse trees ⋮ Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound ⋮ On the Length of Shortest Strings Accepted by Two-way Finite Automata ⋮ Shortest Paths in One-Counter Systems ⋮ Regular Realizability Problems and Context-Free Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The rational index of the Dyck language \(D_ 1^{'*}\)
• Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
• Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
• The Rational Index: A Complexity Measure for Languages

This page was built for publication: Rational indexes of generators of the cone of context-free languages