The rational index of the Dyck language \(D_ 1^{'*}\). (English) Zbl 0632.68072

In order to measure the complexity of languages, the rational index was introduced by L. Boasson and 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 L. Boasson, B. Courcelle, and 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.


68Q45 Formal languages and automata
Full Text: DOI


[1] Boasson, L.; Nivat, M.; Boasson, L.; Nivat, M.; Boasson, L.; Nivat, M., Ordres et types de langage, I, II, III, Notes CRAS, Série A tome 284, Notes CRAS, Série A tome 284, Notes CRAS, Série A tome 284, 703-705, (1977) · Zbl 0354.68107
[2] Boasson, L.; Courcelle, B.; Nivat, M., A new complexity measure, (), 130-138
[3] Boasson, L.; Courcelle, B.; Nivat, M., The rational index, a complexity measure for languages, SIAM J. comput., 10, 2, 284-296, (1981) · Zbl 0469.68083
[4] Gabarro, J., Index rationnel, centre et langages algébriques, (), Rapport L.I.T.P. No. 81-54 · Zbl 0505.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.