We introduce and study a natural extension of Marcus external contextual grammars. This mathematically simple mechanism which generates a proper subclass of simple matrix languages, known to be mildly context-sensitive ones, is still mildly context-sensitive. Furthermore, we get an infinite hierarchy of mildly context-sensitive families of languages. Then we attempt to fill a gap regarding the linguistic relevance of these mechanisms which consists in defining a tree structure on the strings generated by many-dimensional external contextual grammars, and investigate some related (...) issues. Several open problems are finally discussed. (shrink)

The goal of this paper is to survey, in a uniform and systematic way, the main results regarding networks of evolutionary processors reported so far. First, we recall the results concerning the computational power of these networks viewed as language generating devices. Then, we briefly present a few NP-complete problems and recall how they were solved in linear time by networks of evolutionary processors with linearly bounded resources (nodes, ruIes, symbols).