The rational index of the Dyck language \(D_ 1^{'*}\)
type: Item
instance of: scholarly article
title: The rational index of the Dyck language \(D_ 1^{'*}\)
zbMATH Open document ID: 0632.68072
DOI: 10.1016/0304-3975(86)90158-1
author: Jean-Luc Deleage
author: Laurent Pierre
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4028928
zbMATH Keywords: complexity of languages
zbMATH Keywords: rational index
zbMATH Keywords: rational language
zbMATH Keywords: restricted Dyck language
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90158-1
OpenAlex ID: W2064292174
cites work: Q4125811
cites work: Q3868789
cites work: The Rational Index: A Complexity Measure for Languages
cites work: Q4742318
description: scientific article; zbMATH DE number 4028928