Reversibility plays a fundamental role when the possibility to per- form computations with minimal energy dissipation is considered. Many pa- pers on reversible computation have appeared in literature: the most famous are certainly the work of Bennett on (universal) reversible Turing machines and the work of Fredkin and To®oli on conservative...
-
February 23, 2016 (v1)PublicationUploaded on: March 27, 2023
-
December 2015 (v1)Journal article
International audience
Uploaded on: February 28, 2023 -
September 24, 2012 (v1)Conference paper
A new model for the study of ACA dynamical behavior has been introduced. The classical properties of injectivity, surjectivity and expansivity have been adapted to the new setting. Preliminary results show that the injectivity is almost always equal to surjectivity and that both property are almost always implied by expansivity.
Uploaded on: February 28, 2023 -
March 16, 2016 (v1)Publication
In this paper we study some computational properties of spiking neural P systems. In particular, we show that by using nondeterminism in a slightly extended version of spiking neural P systems it is possible to solve in constant time both the numerical NP-complete problem Subset Sum and the strongly NP-complete problem 3-SAT. Then, we show how...
Uploaded on: March 27, 2023 -
December 2013 (v1)Journal article
A new model for the study of asynchronous cellular automata dynamical behavior is introduced with the main purpose of unifying several existing paradigms. The main idea is to measure the set of updating sequences to quantify the dependency of the properties under investigation from them. We propose to use the class of quasi-fair measures,...
Uploaded on: February 28, 2023 -
March 4, 2016 (v1)Publication
We introduce dynamical probabilistic P systems, a variant where probabilities associated to the rules change during the evolution of the system, as a new approach to the analysis and simulation of the behavior of complex systems. We define the notions for the analysis of the dynamics and we show some applications for the investigation of...
Uploaded on: March 27, 2023 -
February 11, 2016 (v1)Publication
In P systems with gemmation of mobile membranes were ex- amined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was also proved that extended gemmating P systems with only pre-dynamical rules are still computationally complete: in this case nine membranes are needed to obtain this...
Uploaded on: March 27, 2023 -
February 2, 2016 (v1)Publication
We improve previously known universality results on enzymatic numerical P systems (EN P systems, for short) working in all-parallel and one-parallel modes. By using a attening technique, we rst show that any EN P system working in one of these modes can be simulated by an equivalent one-membrane EN P system working in the same mode. Then we...
Uploaded on: March 27, 2023 -
April 7, 2016 (v1)Publication
We prove that uniform families of P systems with active membranes operat- ing in polynomial time can solve the whole class of PP decision problems, without using nonelementary membrane division or dissolution rules. This result also holds for families having a stricter uniformity condition than the usual one.
Uploaded on: March 27, 2023 -
March 23, 2016 (v1)Publication
We define space complexity classes in the framework of membrane computing, giving some initial results about their mutual relations and their connection with time complexity classes, and identifying some potentially interesting problems which require further research.
Uploaded on: December 4, 2022 -
April 6, 2017 (v1)Publication
We study a P˘aun's conjecture concerning the unsolvability of NP–complete problems by polarizationless P systems with active membranes in the usual framework, without cooperation, without priorities, without changing labels, using evolution, communication, dissolution and division rules, and working in maximal parallel manner. We also analyse a...
Uploaded on: December 4, 2022 -
March 30, 2016 (v1)Publication
We identify a family of decision problems that are hard for some complexity classes defined in terms of P systems with active membranes working in polynomial time. Furthermore, we prove the completeness of these problems in the case where the systems are equipped with a form of priority that linearly orders their rules. Finally, we...
Uploaded on: December 4, 2022 -
February 3, 2016 (v1)Publication
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.
Uploaded on: December 4, 2022 -
January 21, 2021 (v1)Publication
The first definition of space complexity for P systems was based on an hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A...
Uploaded on: December 4, 2022 -
March 1, 2012 (v1)Journal article
Neutrality of genetic programming Boolean function landscapes is investigated in this paper. Compared with some well known contributions on the same issue, we define new measures that help characterizing neutral landscapes, we use a new sampling methodology, which captures features that are disregarded by uniform random sampling, we introduce...
Uploaded on: December 4, 2022 -
February 15, 2017 (v1)Journal article
International audience
Uploaded on: February 27, 2023 -
December 7, 2016 (v1)Publication
We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions,...
Uploaded on: March 27, 2023 -
January 29, 2016 (v1)Publication
We continue the investigation of the computational power of space- constrained P systems. We show that only a constant amount of space is needed in order to simulate a polynomial-space bounded Turing machine. Due to this result, we propose an alternative de nition of space complexity for P systems, where the amount of information contained in...
Uploaded on: March 27, 2023 -
January 22, 2016 (v1)Publication
We investigate the in uence that the ow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these \monodirectional P systems"...
Uploaded on: March 27, 2023 -
February 3, 2016 (v1)Publication
We show that exponential-space P systems with active membranes characterize the complexity class EXPSPACE. This result is proved by simulating Turing machines working in exponential space via uniform families of P systems with restricted elementary active membranes; the simulation is e cient, in the sense that the time and space required are at...
Uploaded on: March 27, 2023 -
December 18, 2017 (v1)Publication
The literature on membrane computing describes several variants of P systems whose complexity classes C are "closed under exponentiation", that is, they satisfy the inclusion PC C, where PC is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure automatically implies closure under many...
Uploaded on: March 27, 2023 -
March 11, 2019 (v1)Publication
In P systems with active membranes, the question of understanding the power of non-confluence within a polynomial time bound is still an open problem. It is known that, for shallow P systems, that is, with only one level of nesting, non-con uence allows them to solve conjecturally harder problems than con uent P systems, thus reaching PSPACE....
Uploaded on: December 4, 2022 -
April 18, 2007 (v1)Conference paper
We define a set of measures that capture some different aspects of neutrality in evolutionary algorithms fitness landscapes from a qualitative point of view. If considered all together, these measures offer a rather complete picture of the characteristics of fitness landscapes bound to neutrality and may be used as broad indicators of problem...
Uploaded on: February 28, 2023 -
July 12, 2006 (v1)Conference paper
Neutrality of some boolean parity fitness landscapes is investigated in this paper. Compared with some well known contributions on the same issue, we define some new measures that help characterizing neutral landscapes, we use a new sampling methodology, which captures some features that are disregarded by uniform random sampling, and we...
Uploaded on: February 28, 2023 -
March 8, 2016 (v1)Publication
Different stochastic strategies for modeling biological systems with P systems are reviewed in this paper, such as the multi-compartmental approach and dynamical probabilistic P systems. The respective results obtained from the simulations of a test case study (the quorum sensing phenomena in Vibrio Fischeri colonies) are shown, compared and discussed.
Uploaded on: March 27, 2023