scientific article; zbMATH DE number 3999318

From MaRDI portal
Publication:4725772





In our paper About some numerical functions in connection with generative grammars [Ninth Symp. in Informatics Jahorina '85], we discuss the complexity of phrase-structure grammars and we introduce four numerical functions for characterizing the derivations according to such a grammar, namely: the associated function, the characteristic-length function, the depth function and the arc function. We call them derivational functions. Interpretations of some of these functions in terms of graph theory are also developed (by observing that to each derivation an oriented graph can be associated). In this paper we return to these functions for establishing some connections between the depth function of a derivation and the external semi-degree of a vertex of the oriented graph associated to it. Finally we conclude that for a given derivation, the arc function is the largest and the depth function is the least. The minimal value of the arc function is 2 and coincides with the minimal value of the characteristic- length function while the minimal value of the depth function is equal to one. Thus, given a derivation \(D_ n\) of length \(n\geq 2\), if we denote by \(\mu (D_ n)\) the characteristic-length function, by \(Dep(D_ n)\) the depth function and by \(U(D_ n)\) the arc function of \(D_ n\), the following inequalities are true: \(U(D_ n)\geq \mu (D_ n)>Dep(D_ n)\), \(n\geq 2\).












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4725772)