Narrow Results

Reaction systems are well-known formal models of interactions between biochemical reactions. A reaction system is a finite set of triples (reactants, inhibitors, products) that represent chemical reactions, where the reactants, the inhibitors, and the products are objects corresponding to the chemicals. The reactions may facilitate or inhibit each other. A distributed reaction system consists of a finite set of reaction systems that interact with their environment (function in a given context). The environment is a finite set of reactants provided by a context automaton. In the preceding paper, we studied distributed reaction systems where in each step, the context automaton provided a separate set of reactants to the component reaction systems. We assigned languages to these distributed reaction systems and provided representations of some well-known language classes by these constructs. In this paper, the context is provided for the whole distributed reaction system and the component reaction systems distribute the context among each other in different ways (the same context is valid for each component, or the context is split among the components). As in the preceding paper, we assign languages to these new types of distributed reaction systems and provide representations of well-known language classes (the class of right-linear simple matrix languages, the recursively enumerable language class).

Membrane Computing is a recently introduced area of Molecular Computing, where a computation takes place in a membrane structure where multisets of objects evolve according to given rules (they can also pass through membranes). The obtained computing models were called P systems. In basic variants of P systems, the use of objects evolution rules is regulated by a given priority relation; moreover, each membrane has a label and one can send objects to precise membranes, identified by their labels. We propose here a variant where we get rid of both there rather artificial (non-biochemical) features. Instead, we add to membranes and to objects an "electrical charge" and the objects are passed through membranes according to their charge. We prove that such systems are able to characterize the one-letter recursively enumerable languages (equivalently, the recursively enumerable sets of natural numbers), providing that an extra feature is considered: the membranes can be made thicker or thinner (also dissolved) and the communication through a membrane is possible only when its thickness is equal to 1. Several open problems are formulated.

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.