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
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}, mrnumber = {2076403}, zbl = {1082.68049}, language = {en}, url = {http://www.numdam.org/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 - http://www.numdam.org/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 http://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita:2004013/
[1] The algebraic theory of context-free languages, in Computer Programming and Formal Systems, edited by P. Braffort, D. Hirschberg. North-Holland, Amsterdam (1963) 118-161. | Zbl
and ,[2] Eine neue Funktion für Lindenmayer-Systeme. EIK 12 (1976) 515-521. | Zbl
,[3] Numerical parameters of evolutionary grammars, in Jewels are forever, edited by J. Karhumäki, H. Maurer, Gh. Păun, G. Rozenberg. Springer-Verlag, Berlin (1999) 171-181. | Zbl
,[4] Regulated Rewriting in Formal Language Theory. Akademie-Verlag, Berlin and Springer-Verlag, Berlin (1989). | MR | Zbl
and ,[5] Petri nets algorithms in the theory of matrix grammars. Acta Inform. 31 (1994) 719-728. | Zbl
and ,[6] The Mathematical Theory of Context-Free Languages. McGraw Hill Book Comp., New York (1966). | MR | Zbl
,[7] Restricted one-counter machines with undecidable universe problems. Math. Syst. Theory 13 (1979) 181-186. | Zbl
,[8] On a conjecture about slender context-free languages. Theor. Comput. Sci. 132 (1994) 427-434. | Zbl
,[9] On lengths of words in context-free languages. Theor. Comput. Sci. 242 (2000) 327-359. | Zbl
,[10] The growth function of context-free languages. Theor. Comput. Sci. 255 (2001) 601-605. | Zbl
,[11] Characterization of the structure-generating functions of regular sets and the D0L systems. Inform. Control 36 (1978) 85-101. | Zbl
, and ,[12] The structure generating function of some families of languages. Inform. Control 32 (1976) 85-92. | Zbl
and ,
[13]
[14] Semidiscrete context-free languages. Internat. J. Comput. Math. 14 (1983) 3-18. | Zbl
and ,[15] Thin and slender languages. Discrete Appl. Math. 61 (1995) 257-270. | Zbl
and ,[16] Length considerations in context-free languages. Theor. Comput. Sci. 183 (1997) 21-32. | Zbl
,[17] Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). | MR | Zbl
and ,[18] Slender matrix languages, in Developments in Language Theory, edited by G. Rozenberg, W. Thomas. World Scientific, Singapore (2000) 375-385. | Zbl
,Cité par Sources :