Standard

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 › Research › peer-review

Harvard

Shemetova, E, Okhotin, A & Grigorev, S 2022, Rational Index of Languages with Bounded Dimension of Parse Trees. in V Diekert & M Volkov (eds), Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13257 LNCS, Springer Nature, pp. 263-273, 26th International Conference on Developments in Language Theory, DLT 2022, Tampa, United States, 9/05/22. https://doi.org/10.1007/978-3-031-05578-2_21

APA

Shemetova, E., Okhotin, A., & Grigorev, S. (2022). Rational Index of Languages with Bounded Dimension of Parse Trees. In V. Diekert, & M. Volkov (Eds.), Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings (pp. 263-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS). Springer Nature. https://doi.org/10.1007/978-3-031-05578-2_21

Vancouver

Shemetova E, Okhotin A, Grigorev S. Rational Index of Languages with Bounded Dimension of Parse Trees. In Diekert V, Volkov M, editors, Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. Springer Nature. 2022. p. 263-273. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-031-05578-2_21

Author

Shemetova, Ekaterina ; Okhotin, Alexander ; Grigorev, Semyon. / Rational Index of Languages with Bounded Dimension of Parse Trees. Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. editor / Volker Diekert ; Mikhail Volkov. Springer Nature, 2022. pp. 263-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c1a75e8844b64274908b7c12dab9a303,
title = "Rational Index of Languages with Bounded Dimension of Parse Trees",
abstract = "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).",
keywords = "CFL-reachability, Context-free languages, Dimension of a parse tree, Rational index, Strahler number",
author = "Ekaterina Shemetova and Alexander Okhotin and Semyon Grigorev",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 26th International Conference on Developments in Language Theory, DLT 2022 ; Conference date: 09-05-2022 Through 13-05-2022",
year = "2022",
month = may,
doi = "10.1007/978-3-031-05578-2_21",
language = "English",
isbn = "9783031055775",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "263--273",
editor = "Volker Diekert and Mikhail Volkov",
booktitle = "Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings",
address = "Germany",

}

RIS

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