Context-free languages with rational index in \Theta (n^\gamma ) for algebraic numbers \gamma
From MaRDI portal
DOI10.1051/ITA/1990240302751zbMATH Open0701.68068OpenAlexW21512219MaRDI QIDQ3479535FDOQ3479535
Authors: Laurent Pierre, Jean-Marc Farinone 
Publication date: 1990
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92360
Recommendations
- Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
- Rational indexes of generators of the cone of context-free languages
- scientific article; zbMATH DE number 3963215
- The rational index of the Dyck language \(D_ 1^{'*}\)
- Rational index of vector addition systems languages
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Rational Index: A Complexity Measure for Languages
- Transductions des langages de Chomsky
- Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (9)
- 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})}\)
- Rational index of languages defined by grammars with bounded dimension of parse trees
- Regular Realizability Problems and Context-Free Languages
- ON THE CONTEXT-FREENESS OF THE θ-EXPANSIONS OF THE INTEGERS
- On regular realizability problems for context-free languages
- Rational indexes of generators of the cone of context-free languages
- Rational index of vector addition systems languages
- Rational index of languages with bounded dimension of parse trees
This page was built for publication: Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3479535)
