Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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