Rational index of languages defined by grammars with bounded dimension of parse trees

Abstract The rational index \rho_L of a language L is an integer function, where \rho_L is the maximum length of the shortest string in L \cap R, over all regular languages R recognized by n-state nondeterministic finite automata (NFA). This paper investigates the rational index of languages defined by grammars with bounded tree dimension, and shows that itis polynomial in n. More precisely, it is proved that for a context-free grammar with tree dimension bounded by d, its rational index is at most O(n^{2d}), and that this estimation is asymptotically tight, as there exists a grammar with rational index \Theta(n^{2d}). For a multi-component grammar of rank k and with tree dimension bounded by d, the rational index is bounded by O(n^{2kd}), and there exists a grammar with rational index \Omega(n^{2kd}).