Wyniki wyszukiwania - Biblioteka Nauki

1

On Variants of Communicating Distributed H Systems

100%

Frisco P. , Zandron C.

|

2001

|

tom Vol. 48, nr 1

9-20

EN

A recent result shows that a variant of communicating distributed H system with two components can generate recursive enumerable languages. In this variant the filters are a finite union of sets whose number depends upon the simulated system. We prove here that it is possible to obtain the same result using filters testing the presence of couples of symbols. The number of the couples does not depend upon the simulated systems. Moreover we investigate variants of communicating distributed H systems with limitations in the redistribution process.

2

Multiset-Based Self-Assembly of Graphs

80%

Bernardini F. , Brijder R. , Rozenberg G. , Zandron C.

|

tom Vol. 75, nr 1-4

49-75

EN

We present a model for self-assembly of graphs based on multisets and the formalism of membrane systems. The model deals with aggregates of cells which are defined as undirected graphs where a multiset over a fixed alphabet is assigned to each vertex. The evolution of these aggregates is determined by an application of multiset-based aggregation rules to enlarge the current structure as well as an application of membrane-systems-based communication rules to enable cells to exchange objects alongside the edges of the graph. We compare the generative power of self-assembly membrane systems with and without communication rules, and we characterise properties of the sets of graphs generated by these systems. We also introduce two notions of stability for self-assembly processes that capture the idea of having produced a stable structure. Finally, we investigate self-assembly membrane systems where the alphabet is a singleton.

3

Tissue P Systems with Small Cell Volume

71%

Leporati A. , Manzoni L. , Mauri G. , Porreca A. E. , Zandron C.

Fundamenta Informaticae

|

2017

|

tom Vol. 154, nr 1/4

261--275

EN

Traditionally, P systems allow their membranes or cells to grow exponentially (or even more) in volume with respect to the size of the multiset of objects they contain in the initial configuration. This behaviour is, in general, biologically unrealistic, since large cells tend to divide in order to maintain a suitably large surface-area-to-volume ratio. On the other hand, it is usually the number of cells that needs to grow exponentially with time by binary division in order to solve NP-complete problems in polynomial time. In this paper we investigate families of tissue P systems with cell division where each cell has a small volume (i.e., sub-polynomial with respect to the input size), assuming that each bit of information contained in the cell, including both those needed to represent the multiset of objects and the cell label, occupies a unit of volume. We show that even a constant volume bound allows us to reach computational universality for families of tissue P systems with cell division, if we employ an exponential-time uniformity condition on the families. Furthermore, we also show that a sub-polynomial volume does not suffice to solve NP-complete problems in polynomial time, unless the satisfiability problem for Boolean formulae can be solved in sub-exponential time, and that solving an NP-complete problem in polynomial time with logarithmic cell volume implies P = NP.

4

Membrane Division, Oracles, and the Counting Hierarchy

71%

Leporati A. , Manzoni L. , Mauri G. , Porreca A. E. , Zandron C.

Fundamenta Informaticae

|

2015

|

tom Vol. 138, nr 1/2

97--111

EN

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to PPP = P#P, the class of problems solvable in polynomial time by deterministic Turingmachines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between PPP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k.

5

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

71%

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

|

tom 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.

6

On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution

71%

Zandron C. , Leporati A. , Ferretti C. , Mauri G. , Pérez-Jiménez M. J.

|

tom Vol. 87, nr 1

79-91

EN

Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.