Name
Title | ||
|---|---|---|
On differentiation functions, structure functions, and related languages of context-free grammars |
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1051/ita:2004013 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | Field | DocType |
differentiation function,structure function,slender languages | Context-sensitive grammar,Tree-adjoining grammar,Discrete mathematics,Combinatorics,Context-free grammar,Phrase structure grammar,Abstract family of languages,Indexed grammar,Indexed language,Chomsky hierarchy,Algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 3 | 0988-3754 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |
| Victor Mitrana | 2 | 950 | 119.63 |
| Gheorghe Paun | 3 | 2840 | 369.48 |
| Ralf Stiebe | 4 | 85 | 12.78 |