Fundamenta Informaticae - Volume 87, issue 1

Article Type: Other

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. i-ii, 2008

Article Type: Other

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. i-ii, 2008

Authors: Ceterchi, Rodica | Tomescu, Alexandru Ioan

Article Type: Research Article

Abstract: Spiking neural P systems simulate the behavior of neurons sending signals through axons. Recently, some applications concerning Boolean circuits and sorting algorithms have been proposed. In this paper, we study the ability of such systems to simulate a well known parallel sorting model, sorting networks. First, we construct spiking neural P systems which act as comparators of two values, and then show how to assemble these building blocks according to the topology of a sorting network …of N values. In the second part of the paper, we formalize a framework to transform any sorting network into a network composed of comparators which sort n values, 2 < n < N, having the same behaviour as the original sorting network, but using fewer neurons and synapses than the direct simulation. A comparison between the two models proposed here and the sorting model of Ionescu and Sburlan is also given. Show more

Keywords: membrane computing, spiking neural P systems, sorting networks, bitonic sort, optioptimal data layouts

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. 35-48, 2008

Authors: Ciobanu, Gabriel | Resios, Andreas

Article Type: Research Article

Abstract: This paper introduces a new class of membrane systems called simple P systems, and studies their computational complexity. We start by presenting the knapsack problem and its time complexity. Then we study the computational complexity of simple P systems by considering the allocation of resources enabling the parallel application of the rules. We show that the decision version of the resource allocation problem for simple P systems is NP-complete, by using the knapsack problem.

Keywords: membrane systems, knapsack problem, computational complexity

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. 49-59, 2008

Authors: Leporati, Alberto | Gutiérrez-Naranjo, Miguel A.

Article Type: Research Article

Abstract: 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 solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the …problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as SUBSET SUM. In particular, we first propose a semi-uniform family of spiking neural P systems in which every system solves a specific instance of SUBSET SUM. Then, we exploit a technique used to calculate ITERATED ADDITION with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size. Show more

Keywords: Membrane computing, spiking neural P systems, NP-complete problems, Subset Sum

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. 61-77, 2008

Authors: Zandron, Claudio | Leporati, Alberto | Ferretti, Claudio | Mauri, Giancarlo | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: 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. Show more

Keywords: P systems with active membranes, membrane division, membrane dissolution, NP-complete problems, 3-SAT

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. 79-91, 2008

Authors: Zhang, Ge-Xiang | Gheorghe, Marian | Wu, Chao-Zhong

Article Type: Research Article

Abstract: This paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than …quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized. Show more

Keywords: Quantum-inspired evolutionary algorithm, P systems, knapsack problem

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. 93-116, 2008

Authors: Zhang, Xingyi | Zeng, Xiangxiang | Pan, Linqiang

Article Type: Research Article

Abstract: The problem of finding small universal spiking neural P systems was recently investigated by Andrei Păun and Gheorghe Păun, for spiking neural P systems used as devices computing functions and as devices generating sets of numbers. For the first case, a universal spiking neural P system was produced by using 84 neurons for standard rules and using 49 neurons for extended rules. For spiking neural P systems used as generators of sets of numbers, a universal …system with standard rules having 76 neurons, and one with extended rules having 50 neurons were obtained. In this paper, we continue the study of small universal spiking neural P systems and we improve in the number of neurons as follows. The small universal spiking neural P systems use 67 neurons for standard rules and 41 neurons for extended rules in the case of computing functions, and 63 neurons for standard rules and 41 neurons for extended rules in the case of generating sets of numbers. Show more

Keywords: membrane computing, SN P systems, small universal SN P systems

Citation: Fundamenta Informaticae, vol. 87, no. 1, pp. 117-136, 2008