Rational index of languages with bounded dimension of parse trees

DOI10.1007/978-3-031-05578-2_21MaRDI QIDQ2164007zbMATH OpenOpenAlexFDO

Authors Ekaterina Shemetova, Alexander Okhotin, Semyon Grigorev

Publication date 11 August 2022

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

zbMATH Keywords

CFL-reachabilitycontext-free languagesdimension of a parse treerational indexStrahler number

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A Brief History of Strahler Numbers
• Context-free languages with rational index in \Theta (n^\gamma ) for algebraic numbers \gamma
• Convergence of Newton's method over commutative semirings
• 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?)
• Nodes connected by path languages
• On the complexity of L-reachability
• Rational indexes of generators of the cone of context-free languages
• The Rational Index: A Complexity Measure for Languages

Cited in

(4)

• Rational indexes of generators of the cone of context-free languages
• Rational weighted tree languages with storage and the Kleene-Goldstine theorem
• On Rough Approximations of Languages under Infinite Index Indiscernibility Relations
• Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound

This page was built for publication: Rational index of languages 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 Q2164007)