On differentiation functions, structure functions, and related languages of context-free grammars
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 3, pp. 257-267.

Voir la notice de l'article dans Numdam

We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or k-narrow) iff its differentiation function is bounded by a constant (by k). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of the equivalence of grammars with respect to the differentiation function and structure function and prove the decidability of the k-narrowness of context-free grammars. Furthermore, we introduce languages representing the graph of the differentiation and structure function and relate these languages to those of the Chomsky hierarchy.

DOI : 10.1051/ita:2004013
Classification : 68Q45, 68Q50
Mots-clés : differentiation function, structure function, slender languages 
@article{ITA_2004__38_3_257_0,
     author = {Dassow, J\"urgen and Mitrana, Victor and P\u{a}un, Gheorghe and Stiebe, Ralf},
     title = {On differentiation functions, structure functions, and related languages of context-free grammars},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {257--267},
     publisher = {EDP-Sciences},
     volume = {38},
     number = {3},
     year = {2004},
     doi = {10.1051/ita:2004013},
     zbl = {1082.68049},
     mrnumber = {2076403},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004013/}
}
TY  - JOUR
AU  - Dassow, Jürgen
AU  - Mitrana, Victor
AU  - Păun, Gheorghe
AU  - Stiebe, Ralf
TI  - On differentiation functions, structure functions, and related languages of context-free grammars
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2004
SP  - 257
EP  - 267
VL  - 38
IS  - 3
PB  - EDP-Sciences
UR  - https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004013/
DO  - 10.1051/ita:2004013
LA  - en
ID  - ITA_2004__38_3_257_0
ER  - 
%0 Journal Article
%A Dassow, Jürgen
%A Mitrana, Victor
%A Păun, Gheorghe
%A Stiebe, Ralf
%T On differentiation functions, structure functions, and related languages of context-free grammars
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2004
%P 257-267
%V 38
%N 3
%I EDP-Sciences
%U https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004013/
%R 10.1051/ita:2004013
%G en
%F ITA_2004__38_3_257_0
Dassow, Jürgen; Mitrana, Victor; Păun, Gheorghe; Stiebe, Ralf. On differentiation functions, structure functions, and related languages of context-free grammars. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 3, pp. 257-267. doi : 10.1051/ita:2004013. https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004013/

Cité par Sources :