No label defined (Q3777485)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4039331
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4039331 |
Statements
1987
0 references
descriptional complexity
0 references
context-free grammars
0 references
complexity measures
0 references
context-free languages
0 references
grammar class
0 references
normal form
0 references
0.901392102241516
0 references
0.8160926103591919
0 references
0.802598774433136
0 references
0.7950403690338135
0 references
[For the entire collection see Zbl 0633.00024.] The aim of this paper is twofold: first, we generalize some well known results, as we show that the complexity measures Var, Lev, Hei, and Prod are unbounded not only on the whole class of \(\epsilon\)-free context-free languages but on all \(\epsilon\)-free subclasses of \(\epsilon\)-free context-free languages which are similarity classes (general or strict grammatical families) with respect to any corresponding similarity grammar class, that is a general or strict grammar family, producing them. Second, we show that the three areas of language theory, that is, descriptional complexity, grammar form theory and normal form theory are in close connection, as the Var-complexity of a context-free language with respect to a normal form grammar class [in the sense of \textit{D. Wood}, Grammar and L-forms: an introduction (Lect. Notes Comput. Sci. 91) (1980; Zbl 0521.68085)], that is to a strict grammar family of a special two-symbol grammar form, is equal to the measure of boundness of the interpretation which defines the Var-minimal grammar for the language from the grammar form. Moreover, we show that for every natural number n, for every normal form grammar class F, for every descriptional complexity measure K, where \(K\in \{Lev\), Hei, Var, Prod\(\}\), there is an \(\epsilon\)-free context- free language \(L_ K\) such that its K-complexity, with respect to F, is equal to n.
0 references