The rational index of the Dyck language \(D_ 1^{'*}\) (Q1095670)

In order to measure the complexity of languages, the rational index was introduced by \textit{L. Boasson} and \textit{M. Nivat} [C. R. Acad. Sci., Paris, Sér. A. 284, 559-562, 625-628, 703-705 (1977; Zbl 0359.68095, Zbl 0359.68096, Zbl 0354.68107)]. The rational index of a nonempty language L is a function \(\rho_ L\) of \({\mathbb{N}}-\{0\}\) into \({\mathbb{N}}\). The asymptotical behaviour of this function allows to classify languages. More precisely, let n be a positive integer. For each rational language K recognized by a finite nondeterministic automaton with n states and not disjoint with L, let us consider \(\delta_{L\cap K}:\) the length of a shortest word in \(L\cap K\). Then \(\rho_ L(n)\) is the maximum of \(\delta_{L\cap K}\) for all such K. On the other hand, the restricted Dyck language \(D_ 1^{'*}\) is the set of all well-parenthesized words in \(\{a,b\}^*\), considering a and b respectively as left and right parentheses. Then \textit{L. Boasson}, \textit{B. Courcelle}, and \textit{M. Nivat} have shown [Proc. Conf. Theoretical Comput. Sci., Waterloo/Ontario 1977, 130-138 (1977; Zbl 0431.68077)] that \(O(n^ 2)\leq \rho_{D_ 1^{'*}}(n)\leq O(n^ 3)\) and conjectured that \(\rho_{D_ 1^{'*}}(n)=O(n^ 2)\), which we shall prove here.