Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

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

Jürgen DassowVictor MitranaGheorghe PăunRalf Stiebe — 2010

RAIRO - Theoretical Informatics and Applications

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 -narrow) iff its differentiation function is bounded by a constant (by ). 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...

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

Jürgen DassowVictor MitranaGheorghe PăunRalf Stiebe — 2004

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Page 1

Download Results (CSV)