# On differentiation functions, structure functions, and related languages of context-free grammars

Jürgen Dassow; Victor Mitrana; Gheorghe Păun; Ralf Stiebe

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 38, Issue: 3, page 257-267
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topDassow, Jürgen, et al. "On differentiation functions, structure functions, and related languages of context-free grammars." RAIRO - Theoretical Informatics and Applications 38.3 (2010): 257-267. <http://eudml.org/doc/92742>.

@article{Dassow2010,

abstract = {
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.
},

author = {Dassow, Jürgen, Mitrana, Victor, Păun, Gheorghe, Stiebe, Ralf},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Differentiation function; structure function; slender languages; narrow grammars},

language = {eng},

month = {3},

number = {3},

pages = {257-267},

publisher = {EDP Sciences},

title = {On differentiation functions, structure functions, and related languages of context-free grammars},

url = {http://eudml.org/doc/92742},

volume = {38},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 38

IS - 3

SP - 257

EP - 267

AB -
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.

LA - eng

KW - Differentiation function; structure function; slender languages; narrow grammars

UR - http://eudml.org/doc/92742

ER -

## References

top- N. Chomsky and M.P. Schützenberger, 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. Zbl0148.00804
- J. Dassow, Eine neue Funktion für Lindenmayer-Systeme. EIK12 (1976) 515–521. Zbl0348.68047
- J. Dassow, 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. Zbl0944.68088
- J. Dassow and Gh. Păun, Regulated Rewriting in Formal Language Theory. Akademie-Verlag, Berlin and Springer-Verlag, Berlin (1989).
- D. Hauschildt and M. Jantzen, Petri nets algorithms in the theory of matrix grammars. Acta Inform.31 (1994) 719–728. Zbl0834.68064
- S. Ginsburg, The Mathematical Theory of Context-Free Languages. McGraw Hill Book Comp., New York (1966). Zbl0184.28401
- O. Ibarra, Restricted one-counter machines with undecidable universe problems. Math. Syst. Theory13 (1979) 181–186. Zbl0428.03038
- L. Ilie, On a conjecture about slender context-free languages. Theor. Comput. Sci.132 (1994) 427–434. Zbl0938.68707
- L. Ilie, On lengths of words in context-free languages. Theor. Comput. Sci.242 (2000) 327–359. Zbl0944.68099
- R. Incitti, The growth function of context-free languages. Theor. Comput. Sci.255 (2001) 601–605. Zbl0973.68117
- T. Katayama, M. Okamoto and H. Enomoto, Characterization of the structure-generating functions of regular sets and the D0L systems. Inform. Control36 (1978) 85–101. Zbl0378.68042
- W. Kuich and R.K. Shyamasundar, The structure generating function of some families of languages. Inform. Control32 (1976) 85–92. Zbl0338.68054
- M. Kunze, H.J. Shyr and G. Thierrin, h-bounded and semidiscrete languages. Inform. Control51 (1981) 147–187. Zbl0507.68053
- M. Latteux and G. Thierrin, Semidiscrete context-free languages. Internat. J. Comput. Math.14 (1983) 3–18. Zbl0514.68072
- Gh. Păun and A. Salomaa, Thin and slender languages. Discrete Appl. Math.61 (1995) 257–270. Zbl0831.68057
- D. Raz, Length considerations in context-free languages. Theor. Comput. Sci.183 (1997) 21–32. Zbl0911.68097
- A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). Zbl0377.68039
- R. Stiebe, Slender matrix languages, in Developments in Language Theory, edited by G. Rozenberg, W. Thomas. World Scientific, Singapore (2000) 375–385. Zbl0996.68097

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.