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

Efficient Simulation of Reaction Systems on Graphics Processing Units

Nobile M. S., Porreca A. E., Spolaor S., Manzoni L., Cazzaniga P., Mauri G., Besozzi D.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

307--321

EN

Reaction systems represent a theoretical framework based on the regulation mechanisms of facilitation and inhibition of biochemical reactions. The dynamic process defined by a reaction system is typically derived by hand, starting from the set of reactions and a given context sequence. However, this procedure may be error-prone and time-consuming, especially when the size of the reaction system increases. Here we present HERESY, a simulator of reaction systems accelerated on Graphics Processing Units (GPUs). HERESY is based on a fine-grained parallelization strategy, whereby all reactions are simultaneously executed on the GPU, therefore reducing the overall running time of the simulation. HERESY is particularly advantageous for the simulation of large-scale reaction systems, consisting of hundreds or thousands of reactions. By considering as test case some reaction systems with an increasing number of reactions and entities, as well as an increasing number of entities per reaction, we show that HERESY allows up to 29× speed-up with respect to a CPU-based simulator of reaction systems. Finally, we provide some directions for the optimization of HERESY, considering minimal reaction systems in normal form.

3

Membrane Division, Oracles, and the Counting Hierarchy

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

Fundamenta Informaticae

|

2015

|

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.

4

Constant-Space P Systems with Active Membranes

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

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

111--128

EN

We show that a constant amount of space is sufficient to simulate a polynomial-space bounded Turing machine by P systems with active membranes. We thus obtain a new characterisation of PSPACE, which raises interesting questions about the definition of space complexity for P systems. We then propose an alternative definition, where the size of the alphabet and the number of membrane labels of each P system are also taken into account. Finally we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough to even distinguish inputs of the same length.

5

Picture Languages Generated by Assembling Tiles

Bonizzoni P., Ferretti C., Mary A. R. S., Mauri G.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

77-93

EN

We propose a new formalism for generating picture languages based on an assembly mechanism of tiles that uses rules having a context and a replacement site. More precisely, a picture language will be generated from a finite set of initial pictures by iteratively applying rewriting rules from a given finite set of rules, called a tiling rule system (TRuS system). We prove that the TRuS systems have a greater generative capacity than the tiling systems of Giammarresi and Restivo. This is due mainly to the use of the notion of replacement site, but we further characterize the difference between these systems by comparing them to Wang systems.

6

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

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

Fundamenta Informaticae

|

2008

|

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.

7

Supporting Action-at-a-distance in Situated Cellular Agents

Bandini S., Mauri G., Vizzari G.

Fundamenta Informaticae

|

2006

|

Vol. 69, nr 3

251-271

EN

The aim of this paper is to describe algorithms and structures required to support action-at-a-distance in Situated Cellular Agents (SCA). This model provides the possibility to define heterogeneous entities placed in regular or irregular spatial infrastructures. Different mechanisms supporting field diffusion within these structures will be described and analyzed, with reference to their performance. A sample application of SCA model (a variation of Conway's Game of Life) will also be illustrated, while a more complex usage of action-at-a-distance for pedestrian simulation will be sketched.

8

Reversible P Systems to Simulate Fredkin Circuits

Leporati A., Zandron C., Mauri G.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 4

529-548

EN

We introduce energy-based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Basing upon the seminal paper of Fredkin and Toffoli on conservative logic, we first show how energy-based P systems can be used to simulate the Fredkin gate, a reversible and conservative three-input/three-output boolean gate which is functionally complete for boolean logic. Then, we show how any reversible Fredkin circuit can be simulated by energy-based P systems whose number of membranes is independent of the number of gates occurring in the simulated circuit. The simulating P systems turn out to be themselves reversible and conservative.