Rational index of languages defined by grammars with bounded dimension of parse trees

DOI10.1007/S00224-023-10159-3MaRDI QIDQ6580079zbMATH OpenFDO

Authors Ekaterina Shemetova, Alexander Okhotin, Semyon Grigorev

Publication date 29 July 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

context-free grammarsmultiple context-free grammarsStrahler numberrational indexdimension of a parse tree\(k\)-caterpillar treesquasi-rational languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

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

Cites work

• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 4205991 (Why is no real title available?)
• scientific article; zbMATH DE number 3640873 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 7439739 (Why is no real title available?)
• A Brief History of Strahler Numbers
• A tale of conjunctive grammars
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Context-sensitive data-dependence analysis via linear conjunctive language reachability
• Convergence of Newton’s Method over Commutative Semirings
• Decidability and shortest strings in formal languages
• Longer shortest strings in two-way finite automata
• Membership problems in finite groups
• Nodes connected by path languages
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• On multiple context-free grammars
• On the complexity of L-reachability
• On the index of a context-free grammar and language
• On the length of shortest strings accepted by two-way finite automata
• Parallel complexity of logical query programs
• Parikh's theorem: a simple and direct automaton construction
• Ramanujan Primes and Bertrand's Postulate
• Rational indexes of generators of the cone of context-free languages
• Regular Realizability Problems and Context-Free Languages
• Regular expressions: new results and open problems
• Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
• The Rational Index: A Complexity Measure for Languages
• \(O_n\) is an \(n\)-MCFL

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)