Rational index of languages with bounded dimension of parse trees

DOI10.1007/978-3-031-05578-2_21OpenAlexW4285128581MaRDI QIDQ2164007

Ekaterina Shemetova, Semyon Grigorev, Alexander Okhotin

Publication date: 11 August 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-05578-2_21

zbMATH Keywords

context-free languagesStrahler numberrational indexCFL-reachabilitydimension of a parse tree

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound

Cites Work

• Convergence of Newton's method over commutative semirings
• Rational indexes of generators of the cone of context-free languages
• Shortest Paths in One-Counter Systems
• Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $
• The Rational Index: A Complexity Measure for Languages
• Nodes Connected by Path Languages
• A Brief History of Strahler Numbers
• On the Complexity of L-reachability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Rational index of languages with bounded dimension of parse trees