Narrow Results

Operations with membranes are essential both in brane calculi and in membrane computing. In this paper we take four basic operations from brane calculi, pino, exo, mate, drip, we express them in terms of the membrane computing formalism, and then we investigate the computing power of the P systems using the mate, drip operations as unique evolution rules. All operations are controlled by – and make evolve – multisets of protein-objects embedded in the membranes themselves (not contained in the compartments of the cell, as standard in membrane computing; all compartments delimited by membranes are here empty). Somewhat surprisingly, for systems which use the mate, drip operations we obtain the Turing completeness. The power of P systems based on other operations remains to be investigated.

Matrix grammars are one of the classical topics of formal languages, more specifically, regulated rewriting. Although this type of control on the work of context-free grammars is one of the earliest, matrix grammars still raise interesting questions (not to speak about old open problems in this area). One such class of problems concerns the leftmost derivation (in grammars without appearance checking). The main point of this paper is the systematic study of all possibilities of defining leftmost derivation in matrix grammars. Twelve types of such a restriction are defined, only four of which being discussed in literature. For seven of them, we find a proof of a characterization of recursively enumerable languages (by matrix grammars with arbitrary context-free rules but without appearance checking). Other three cases characterize the recursively enumerable languages modulo a morphism and an intersection with a regular language. In this way, we solve nearly all problems listed as open on page 67 of the monograph [7], which can be seen as the main contribution of this paper.

Moreover, we find a characterization of the recursively enumerable languages for matrix grammars with the leftmost restriction defined on classes of a given partition of the nonterminal alphabet.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho. is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results. applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho, is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results, applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.