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 languageEnglish
Title of host publicationDevelopments in Language Theory - 26th International Conference, DLT 2022, Proceedings
EditorsVolker Diekert, Mikhail Volkov
PublisherSpringer Nature
Pages263-273
Number of pages11
ISBN (Print)9783031055775
DOIs
StatePublished - May 2022
Event26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, United States
Duration: 9 May 202213 May 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13257 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Developments in Language Theory, DLT 2022
Country/TerritoryUnited States
CityTampa
Period9/05/2213/05/22

    Research areas

  • CFL-reachability, Context-free languages, Dimension of a parse tree, Rational index, Strahler number

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 95348783