Wyniki wyszukiwania - BazTech

1

Variants of Small Universal P Systems with Catalysts

Alhazov A., Freund R.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

227--250

EN

Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky’s reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we are able to transformthe universalmachines U22 and U20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result.

2

Length P Systems

Alhazov A., Freund R., Ivanov S.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

17--37

EN

In this paper, we examine P systems with a linear membrane structure, i.e., P systems in which only one membrane is elementary and the output of which is read out as the sequence of membrane labels in the halting configuration or vectors/numbers represented by this sequence. We investigate the computational power of such systems, depending on the number of membrane labels, kinds of rules used, and some other possible restrictions. We prove that two labels, elementary membrane creation and dissolution, together with the usual send-in and send-out rules, suffice to achieve computational completeness, even with the restriction that only one object is allowed to be present in any configuration of the system. On the other hand, limiting the number of labels to one reduces the computational power to the regular sets of non-negative integers. We also consider other possible variants of such P systems, e.g., P systems in which all membranes but one have the same label, P systems with membrane duplication rules, or systems in which multiple objects are allowed to be present in a configuration, and we describe the computational power of all these models.

3

Antimatter as a Frontier of Tractability in Membrane Computing

Díaz-Pernil D., Peña-Cantillana F., Alhazov A., Freund R., Gutiérrez-Naranjo M. A.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

83--96

EN

It is well known that the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary and nonelementary membranes is exactly the complexity class P (see [9], Theorem 2). In this paper, we prove that if such a P systems model is endowed with antimatter and annihilation rules, then NP problems can be solved, even without non-elementary membrane division. In this way, antimatter is shown to be a frontier of tractability in Membrane Computing.

4

P Systems with Insertion and Deletion Exo-Operations

Alhazov A., Krassovitskiy A., Rogozhin Y., Verlan S.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

13-28

EN

It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case.

5

Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions

Alhazov A., Oswald M., Freund R., Verlan S.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

17-34

EN

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.

6

On Networks of Evolutionary Processors with Nodes of Two Types

Alhazov A., Martin-Vide C., Truthe B., Dassow J., Rogozhin Y.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

1-15

EN

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.

7

(Tissue) P Systems with Unit Rules and Energy Assigned to Membranes

Alhazov A., Freund R., Leporati A., Oswald M., Zandron C.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 4

391-408

EN

We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand, when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step, only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars.

8

Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes

Alhazov A., Martin-Vide C., Pan L.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 2

67--77

EN

P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. Recently, Petr Sosík has shown that a semi-uniform family of P systems with active membranes and 2-division is able to solve the PSPACE-complete problem QBF-SAT in linear time; he has also conjectured that the membrane dissolving rules of the (d) type may be omitted, but probably not the (f) type rules for non-elementary membrane division. In this paper, we partially confirm the conjecture proving that dissolving rules are not necessary. Moreover, the construction is now uniform. It still remains open whether or not non-elementary membrane division is needed.