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 QIDQ6580079
Alexander Okhotin, Semyon Grigorev, Ekaterina Shemetova
Publication date: 29 July 2024
Published in: Theory of Computing Systems (Search for Journal in Brave)
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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Parallel complexity of logical query programs
- On multiple context-free grammars
- Rational indexes of generators of the cone of context-free languages
- A tale of conjunctive grammars
- Parikh's theorem: a simple and direct automaton construction
- Longer shortest strings in two-way finite automata
- \(O_n\) is an \(n\)-MCFL
- Ogden's lemma, multiple context-free grammars, and the control language hierarchy
- Shortest Paths in One-Counter Systems
- Ramanujan Primes and Bertrand's Postulate
- The Rational Index: A Complexity Measure for Languages
- Convergence of Newton’s Method over Commutative Semirings
- On the Length of Shortest Strings Accepted by Two-way Finite Automata
- Nodes Connected by Path Languages
- Decidability and Shortest Strings in Formal Languages
- Context-sensitive data-dependence analysis via linear conjunctive language reachability
- A Brief History of Strahler Numbers
- On the Complexity of L-reachability
- Regular Realizability Problems and Context-Free Languages
- On the index of a context-free grammar and language
- 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)
