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 - Informatique Théorique et Applications (2004)

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

Abstract

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

How to cite

top

Dassow, Jürgen, et al. "On differentiation functions, structure functions, and related languages of context-free grammars." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.3 (2004): 257-267. <http://eudml.org/doc/245023>.

@article{Dassow2004,
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 - Informatique Théorique et Applications},
keywords = {differentiation function; structure function; slender languages; narrow grammars},
language = {eng},
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/245023},
volume = {38},
year = {2004},
}

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
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/245023
ER -

References

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

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.