Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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).
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings |
| Редакторы | Volker Diekert, Mikhail Volkov |
| Издатель | Springer Nature |
| Страницы | 263-273 |
| Число страниц | 11 |
| ISBN (печатное издание) | 9783031055775 |
| DOI | |
| Состояние | Опубликовано - мая 2022 |
| Событие | 26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, Соединенные Штаты Америки Продолжительность: 9 мая 2022 → 13 мая 2022 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 13257 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 26th International Conference on Developments in Language Theory, DLT 2022 |
|---|---|
| Страна/Tерритория | Соединенные Штаты Америки |
| Город | Tampa |
| Период | 9/05/22 → 13/05/22 |
ID: 95348783