DOI

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 мая 202213 мая 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/2213/05/22

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 95348783