Issue |
RAIRO-Theor. Inf. Appl.
Volume 38, Number 3, July-September 2004
|
|
---|---|---|
Page(s) | 257 - 267 | |
DOI | https://doi.org/10.1051/ita:2004013 | |
Published online | 15 June 2004 |
On differentiation functions, structure functions, and related languages of context-free grammars
1
Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany; dassow@iws.cs.uni-magdeburg.de.; stiebe@iws.cs.uni-magdeburg.de.
2
University of Bucharest, Institute of Mathematics,
Str. Academiei 14, 70109 Bucuresti, Romania.
3
Rovira i Virgili University, Research Group in Mathematical Linguistics,
Pça. Imperial Tarraco 1, 43005, Tarragona, Spain; vmi@fll.urv.es.
4
Institute of Mathematics of the Romanian Academy,
PO Box 1–764, 70700 Bucuresti, Romania; George.Paun@imar.ro.
Received:
29
August
2001
Accepted:
10
April
2004
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.
Mathematics Subject Classification: 68Q45 / 68Q50
Key words: Differentiation function / structure function / slender languages
© EDP Sciences, 2004
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.