Rational index of languages defined by grammars with bounded dimension of parse trees
From MaRDI portal
Publication:6580079
DOI10.1007/S00224-023-10159-3zbMATH Open1547.68381MaRDI QIDQ6580079FDOQ6580079
Authors: Ekaterina Shemetova, Alexander Okhotin, Semyon Grigorev 
Publication date: 29 July 2024
Published in: Theory of Computing Systems (Search for Journal in Brave)
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
- Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
- The rational index of the Dyck language \(D_ 1^{'*}\)
- scientific article; zbMATH DE number 3557672
context-free grammarsmultiple context-free grammarsStrahler numberrational indexdimension of a parse tree\(k\)-caterpillar treesquasi-rational languages
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parallel complexity of logical query programs
- Ramanujan Primes and Bertrand's Postulate
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Regular expressions: new results and open problems
- On multiple context-free grammars
- Rational indexes of generators of the cone of context-free languages
- The Rational Index: A Complexity Measure for Languages
- Parikh's theorem: a simple and direct automaton construction
- On the index of a context-free grammar and language
- Title not available (Why is that?)
- A tale of conjunctive grammars
- A Brief History of Strahler Numbers
- On the complexity of L-reachability
- Context-sensitive data-dependence analysis via linear conjunctive language reachability
- Longer shortest strings in two-way finite automata
- Decidability and shortest strings in formal languages
- Regular Realizability Problems and Context-Free Languages
- \(O_n\) is an \(n\)-MCFL
- Convergence of Newton’s Method over Commutative Semirings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nodes connected by path languages
- Ogden's lemma, multiple context-free grammars, and the control language hierarchy
- On the length of shortest strings accepted by two-way finite automata
- Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
- Membership problems in finite groups
This page was built for publication: Rational index of languages defined by grammars with bounded dimension of parse trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6580079)
