Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Rational Index of Languages with Bounded Dimension of Parse Trees. / Shemetova, Ekaterina; Okhotin, Alexander; Grigorev, Semyon.
Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. ed. / Volker Diekert; Mikhail Volkov. Springer Nature, 2022. p. 263-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
}
TY - GEN
T1 - Rational Index of Languages with Bounded Dimension of Parse Trees
AU - Shemetova, Ekaterina
AU - Okhotin, Alexander
AU - Grigorev, Semyon
N1 - Publisher Copyright: © 2022, Springer Nature Switzerland AG.
PY - 2022/5
Y1 - 2022/5
N2 - The rational index ρL of a language L is an integer function, where ρL(n) is the maximum length of the shortest string in L∩ R, over all regular languages R recognized by n-state nondeterministic finite automata (NFA). This paper investigates the rational index of languages defined by (context-free) grammars with bounded tree dimension, and shows that it is of polynomial in n. More precisely, it is proved that for a grammar with tree dimension bounded by d, its rational index is O(n2 d), and that this estimation is asymptotically tight, as there exists a grammar with rational index Θ(n2 d).
AB - The rational index ρL of a language L is an integer function, where ρL(n) is the maximum length of the shortest string in L∩ R, over all regular languages R recognized by n-state nondeterministic finite automata (NFA). This paper investigates the rational index of languages defined by (context-free) grammars with bounded tree dimension, and shows that it is of polynomial in n. More precisely, it is proved that for a grammar with tree dimension bounded by d, its rational index is O(n2 d), and that this estimation is asymptotically tight, as there exists a grammar with rational index Θ(n2 d).
KW - CFL-reachability
KW - Context-free languages
KW - Dimension of a parse tree
KW - Rational index
KW - Strahler number
UR - http://www.scopus.com/inward/record.url?scp=85130210888&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/d4363465-f1e6-3be4-984d-66a655b0afec/
U2 - 10.1007/978-3-031-05578-2_21
DO - 10.1007/978-3-031-05578-2_21
M3 - Conference contribution
AN - SCOPUS:85130210888
SN - 9783031055775
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 263
EP - 273
BT - Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings
A2 - Diekert, Volker
A2 - Volkov, Mikhail
PB - Springer Nature
T2 - 26th International Conference on Developments in Language Theory, DLT 2022
Y2 - 9 May 2022 through 13 May 2022
ER -
ID: 95348783