Wyniki wyszukiwania - BazTech

1

Tissue P Systems with Small Cell Volume

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

Fundamenta Informaticae

|

2017

|

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.

2

Tissue P Systems with Protein on Cells

Song B., Pan L., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2016

|

Vol. 144, nr 1

77--107

EN

Tissue P systems are a class of distributed parallel computing devices inspired by biochemical interactions between cells in a tissue-like arrangement, where objects can be exchanged by means of communication channels. In this work, inspired by the biological facts that the movement of most objects through communication channels is controlled by proteins and proteins can move through lipid bilayers between cells (if these cells are fused), we present a new class of variant tissue P systems, called tissue P systems with protein on cells, where multisets of objects (maybe empty), together with proteins between cells are exchanged. The computational power of such P systems is studied. Specifically, an efficient (uniform) solution to the SAT problem by using such P systems with cell division is presented. We also prove that any Turing computable set of numbers can be generated by a tissue P system with protein on cells. Both of these two results are obtained by such P systems with communication rules of length at most 4 (the length of a communication rule is the total number of objects and proteins involved in that rule).

3

An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

Pérez-Jiménez M. J., Sosík P.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

45--60

EN

A membrane system (P system) is a distributed computingmodel inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non–efficiency to efficiency, assuming that P 6= NP.

4

A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem

Niu Y., Pan L., Pérez-Jiménez M.J., Font M. R.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 2

179-188

EN

A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NPcomplete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules.

5

Modelling Grammar Systems by Tissue P Systems Working in the Sequential Mode

Freund R., Oswald M.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

305-323

EN

We consider tissue P systems where rules are applied when moving through a channel from one cell to another one. In a very general manner (i.e., working on arbitrary objects as strings, arrays, graphs, etc.), these tissue P systems equipped with the sequential derivation mode allow for the representation of hybrid co-operating grammar systems using the classic basic derivation modes *,t and ? k,=k, ^(3) k, for k ^(3) 1, as well as the internally hybrid modes ( ^(3) kU` ? l), for k,l Î \mathbbN , k ? l, and (tU` ? k) , ( tU` = k) , (tU` ^(3) k) , for k ^(3) 1. Moreover, we also show how these tissue P systems working in the sequential mode allow for the simulation of random context grammars, too.