Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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).
Original language | English |
---|---|
Title of host publication | Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings |
Editors | Volker Diekert, Mikhail Volkov |
Publisher | Springer Nature |
Pages | 263-273 |
Number of pages | 11 |
ISBN (Print) | 9783031055775 |
DOIs | |
State | Published - May 2022 |
Event | 26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, United States Duration: 9 May 2022 → 13 May 2022 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 13257 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 26th International Conference on Developments in Language Theory, DLT 2022 |
---|---|
Country/Territory | United States |
City | Tampa |
Period | 9/05/22 → 13/05/22 |
ID: 95348783