LEPORATI , Alberto

We propose to use tissue-like P systems as a tool to model and analyse the security properties of ¯rewall systems. The idea comes from a clear analogy between firewall rules and P systems rules: they both modify and or move objects (data packets, or symbols of an alphabet) among the regions of the system. The use of P systems for modeling...

Most of the works concerning cryptographic applications of cellular automata (CA) focus on the analysis of the underlying local rules, interpreted as boolean functions. In this paper, we investigate the cryptographic criteria of CA global rules by considering them as vectorial boolean functions. In particular, we prove that the 1-resiliency...

We propose a genetic algorithm (GA) to search for plateaued boolean functions, which represent suitable candidates for the design of stream ciphers due to their good cryptographic properties. Using the spectral inversion technique introduced by Clark, Jacob, Maitra and Stanica, our GA encodes the chromosome of a candidate solution as a...

In this paper, we investigate the periods of preimages of spatially periodic configurations in linear bipermutive cellular automata (LBCA). We first show that when the CA is only bipermutive and y is a spatially periodic configuration of period p, the periods of all preimages of y are multiples of p. We then present a connection between...

We propose three quantum algorithms to solve the 3-SAT NP-complete decision problem. The first algorithm builds, for any instance Á of 3-SAT, a quantum Fredkin circuit that computes a superposition of all classical evaluations of Á in a given output line. Similarly, the second and third algorithms compute the same superposition on a given...

We present a Particle Swarm Optimizer for generating boolean functions with good cryptographic properties. The proposed algorithm updates the particles positions while preserving their Hamming weights, to ensure that the generated functions are balanced, and it adopts Hill Climbing to further improve their nonlinearity and correlation immunity....

We consider the problem of enumerating pairs of bipermutive cellular automata (CA) which generate orthogonal Latin squares. Since the problem has already been settled for bipermutive CA with linear local rules, we address the general case of nonlinear rules, which could be interesting for cryptographic applications such as the design of...

We consider spiking neural P systems as devices which can be used to perform some basic arithmetic operations, namely addition, subtraction, comparison and multiplication by a fixed factor. The input to these systems are natural numbers expressed in binary form, encoded as appropriate sequences of spikes. A single system accepts as inputs...

Prague, Czech Republic. Springer, 9618, pp.592-602, 2016, Lecture Notes in Computer Science. <ht

Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre-computed resources are given in advance, provided that their structure is regular and they do not contain neither hidden information that simplify the...

Recently we have considered the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption that some (possibly exponentially large) pre-computed resources are given in advance. In this paper we continue this research line, and we investigate the possibility of solving numerical...

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

We investigate the computational power of energy-based P systems, a model of membrane systems where a fixed amount of energy is associated with each object and the rules transform single objects by adding or removing energy from them. We answer recently proposed open questions about the power of such systems without priorities associated to the...

We prove that asynchronous P systems with active membranes without divi- sion rules can be simulated by place/transition Petri nets, and hence are computationally weaker than Turing machines. This result holds even if the synchronisation mechanisms provided by electrical charges and membrane dissolution are exploited.

We consider spiking neural P systems as devices which can be used to perform some basic arithmetic operations, namely addition, subtraction, comparison and multiplica- tion by a fixed factor. The input to these systems are natural numbers expressed in binary form, encoded as appropriate sequences of spikes. A single system accepts as inputs...

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

We investigate sets of Mutually Orthogonal Latin Squares (MOLS) generated by Cellular Automata (CA) over finite fields. After introducing how a CA defined by a bipermutive local rule of diameter $d$ over an alphabet of $q$ elements generates a Latin square of order $q^{d-1}$, we study the conditions under which two CA generate a pair of...

Current P systems which solve NP-complete numerical problems represent the instances of the problems in unary notation. However, in classical complexity theory, based upon Turing machines, switching from binary to unary encoded instances generally corresponds to simplify the problem. In this paper we show that, when working with P systems, we...

Current P systems which solve NP–complete numerical problems represent instances in unary notation. In classical complexity theory, based upon Turing machines, switching from binary to unary encoded instances gen erally corresponds to simplify the problem. In this paper we show that this does not occur when working with P systems. Namely, we...

International audience

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.

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.

International audience