Search

We consider tissue P systems working on vesicles of multisets with the very simple operations of insertion, deletion, and substitution of single objects. With the whole multiset being enclosed in a vesicle, sending it to a target cell can be indicated in those simple rules working on the multiset. As derivation modes we consider the sequential mode, where exactly one rule is applied in a derivation step, and the set maximal mode, where in each derivation step a non-extendable set of rules is applied. With the set maximal mode, computational completeness can already be obtained with tissue P systems having a tree structure, whereas tissue P systems even with an arbitrary communication structure are not computationally complete when working in the sequential mode. Adding polarizations (-1, 0, 1 are sufficient) allows for obtaining computational completeness even for tissue P systems working in the sequential mode.

In this paper we focus on two weak forms of cooperation in P systems, namely, catalytic rules and matter/anti-matter annihilation rules. These variants of P systems both are computationally complete, while the corresponding rule complexity turns out to be of special interest. For establishing considerably small universal P systems in both cases, we found two suitable tools: generalized register machines and generalized counter automata. Depending on the features used in the different variants, we construct several small universal P systems.

This work presents the application of new parallelization methods based on membrane-quantum hybrid computing to graph isomorphism problem solving. Applied membrane-quantum hybrid computational model was developed by authors. Massive parallelism of unconventional computing is used to implement classic brute force algorithm efficiently. This approach does not suppose any restrictions of considered graphs types. The estimated performance of the model is less then quadratic that makes a very good result for the problem of \textbf{NP} complexity.

This work presents a hybrid model of high performance computations. The model is based on membrane system (P~system) where some membranes may contain quantum device that is triggered by the data entering the membrane. This model is supposed to take advantages of both biomolecular and quantum paradigms and to overcome some of their inherent limitations. The proposed approach is demonstrated through two selected problems: SAT, and image retrieving.

Networks of evolutionary processors (NEPs) are distributed word rewriting systems typically viewed as language generators. Each node contains a set of words, a set of operations (typically insertion, deletion or rewriting of one symbol with another one), an input filter and an output filter. The purpose of this paper is to overview existing models of NEPs, their variants and developments. In particular, besides the basic model, hybrid networks of evolutionary processors (HNEPs) have been extensively studied. In HNEPs, operations application might be restricted to specific end of the string, but the filters are random-context conditions (they were regular in the basic model). We will also cover the literature on the so-called obligatory HNEPs, i.e., ones where the operations are obligatory: the string that cannot be rewritten is not preserved. Some specific aspects that we pay attention to are: computational universality and completeness, the topology of the underlying graph, the number of nodes, the power of filters.

In this paper we study a notion of self-stabilization, inspired from biology and engineering. Multiple variants of formalization of this notion are considered, and we discuss how such properties affect the computational power of multiset rewriting systems.

We describe the investigations on natural computing in the Institute of Mathematics and Computer Science of the Academy of Sciences of Moldova during last fifteen years. Most of these investigations are inspired by results and ideas belonging to Corresponding Member of the Romanian Academy Gheorghe Paun.

The focus of this paper is the family of languages generated by transitional non-cooperative P systems without further ingredients. This family can also be defined by so-called time yields of derivation trees of context-free grammars. In this paper we prove that such languages can be parsed in polynomial time, where the degree of polynomial may depend on the number of rules and on the size of the alphabet.

It is known that the satisfiability problem ({\tt SAT}) can be efficiently solved by a uniform family of P systems with active membranes with two polarizations working in a maximally parallel way. We study P systems with active membranes without non-elementary membrane division, working in minimally parallel way. The main question we address is what number of polarizations is sufficient for an efficient computation depending on the types of rules used. In particular, we show that it is enough to have four polarizations, sequential evolution rules changing polarizations, polarizationless non-elementary membrane division rules and polarizationless rules of sending an object out. The same problem is solved with the standard evolution rules, rules of sending an object out and polarizationless non-elementary membrane division rules, with six polarizations. It is an open question whether these numbers are optimal.

The aim of this article is the formalization of inflection process for the Romanian language using the model of P systems with cooperative string replication rules, which will make it possible to automatically build the morphological lexicons as a base for different linguistic applications.

A hybrid network of evolutionary processors (an HNEP) is a graph where each node is associated with an evolutionary processor (a special rewriting system), a set of words, an input filter and an output filter. Every evolutionary processor is given with a finite set of one type of point mutations (an insertion, a deletion or a substitution of a symbol) which can be applied to certain positions of a string over the domain of the set of these rewriting rules. The HNEP functions by rewriting the words that can be found at the nodes and then re-distributing the resulting strings according to a communication protocol based on a filtering mechanism. The filters are defined by certain variants of random-context conditions. In this paper we complete investigation of HNEPs with one node and present a precise description of languages generated by them.

Evolution of the informatization notion (which assumes automation of majority of human activities applying computers, computer networks, information technologies) towards the notion of {\it Global Information Society} (GIS) challenges the determination of new paradigms of society: automation and intellectualization of production, new level of education and teaching, formation of new styles of work, active participation in decision making, etc. To assure transition to GIS for any society, including that from Republic of Moldova, requires both special training and broad application of progressive technologies and information systems. Methodological aspects concerning impact of GIS creation over the citizen, economic unit, national economy in the aggregate demands a profound study. Without systematic approach to these aspects the GIS creation would have confront great difficulties. Collective of researchers from the Institute of Mathematics and Computer Science (IMCS) of Academy of Sciences of Moldova, which work in the field of computer science, constitutes the center of advanced researches and activates in those directions of researches of computer science which facilitate technologies and applications without of which the development of GIS cannot be assured.

It is known that P systems with two membranes and minimal symport/antiport rules are “almost” computationally complete as generators of number or vector sets. Interpreting the result of the computation as the sequence of terminal symbols sent to the environment, we show that P systems with two membranes and symport rules of weight two or symport/antiport rules of weight one generate all recursively enumerable languages.

We consider a new kind of computational device like Turing machine, so-called circular Post machines with a circular tape and moving in one direction only, introduced recently by the second and the third authors. Using 2-tag systems we construct new nine small universal machines of this kind.

In this paper we give the solution methods for a multicriterial transportation problem of a nonlinear type. We would like to note that the problems of this type do not have any classical solution algorithms. The article consists of two parts dealing with 2 and 3 objectives respectively, one being non-linear of ``bottleneck'' type, and the rest being linear ones. Definitions of efficient and extreme efficient solutions are introduced and a separate solution algorithms for these models are described. The correctness theorems for the algorithms are proved. Examples solved by the computer programs implementing the algorithms are included.