Two methods for multicriteria hierarchization of discrete alternatives
Some consequences of a result of Ehrenfeucht and Rozenberg
On simple matrix languages versus scattered context languages
Some further remarks on the family of finite index matrix languages
Two infinite hierarchies of languages defined by branching grammars
Two theorems about Galiukschov semicontextual languages
On the generative capacity of colonies
On the syntactic complexity of parallel communicating grammar systems
Independent instances for some undecidable problems
Regulated Galiukschov semicontextual grammars
Further remarks on the complexity of regulated rewriting
De lo viejo a lo nuevo en Teoría de la Computación: teoría de lenguajes formales y de autómatas vs. computación molecular.
On differentiation functions, structure functions, and related languages of context-free grammars
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 equivalence...
On parallel deletions applied to a word
On differentiation functions, structure functions, and related languages of context-free grammars
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...
Page 1