Search

Membrane computing is an unconventional computing paradigm that has gained much attention in recent decades because of its massively parallel character and its usefulness to build models of complex systems. However, until now, there was no generic hardware implementation of P systems. Computational frameworks to execute P systems up to this day rely on the simulation of the parallel working mechanisms of P systems by inherently sequential algorithms. Such algorithms can then be implemented as is or can be parallelized, up to a certain point, to run on parallel computers. However, this is not as efficient as a dedicated parallel hardware implementation. There have been ad hoc implementations of particular P systems for parallel hardware, but they lack to be problem-generic or they are not scalable enough to implement large P systems. In this paper, a first intrinsically parallel hardware architecture to implement generic P system models is introduced. It is designed to be straightforwardly implemented in programmable logic circuits like FPGAs. The feasibility and correct execution of our architecture has been verified by means of a simulator, and several simulation results for different P system examples have been analysed to foresee the pros and cons of this design.

Membrane computing is a massively parallel and non-deterministic bioinspired computing paradigm whose models are called P systems. Validating and testing such models is a challenge which is being overcome by developing simulators. Regardless of their heterogeneity, such simulators require to read and interpret the models to be simulated. To this end, P-Lingua is a high-level P system definition language which has been widely used in the last decade. The P-Lingua ecosystem includes not only the language, but also libraries and software tools for parsing and simulating membrane computing models. Each version of P-Lingua supported new types or variants of P systems. This leads to a shortcoming: Only a predefined list of variants can be used, thus making it difficult for researchers to study custom ones. Moreover, derivation modes cannot be user-defined, i.e, the way in which P system computations should be generated is determined by the simulation algorithm in the source code. The main contribution of this paper is a completely new design of the P-Lingua language, called P-Lingua 5, in which the user can define custom variants and derivation modes, among other improvements such as including procedural programming and simulation directives. It is worth mentioning that it has backward-compatibility with previous versions of the language. A completely new set of command-line tools is provided for parsing and simulating P-Lingua 5 files. Finally, several examples are included in this paper covering the most common P system types.

DP is the class of problems that are the differences between two languages from NP. Most difficult problems from DP are called DP-complete problems, that can be seen as the conjunction of an NP-complete problem and a co-NP-complete problem. It is easy to see that the problem P vs NP is equivalent to the problem P vs DP, and therefore DP-complete problems would be better candidates to attack the conjecture, since they seem to be harder than NP-complete problems. In this paper, a methodology to transform an efficient solution of an NP-complete problem into an efficient solution of a DP-complete problem is applied. More precisely, a solution to SAT is given by means of a uniform family of recognizer polarizationless P systems with active membranes with dissolution rules and division rules for both elementary and non-elementary membranes, and later it is transformed into a solution to the problem SAT-UNSAT.

Dendrite P systems (DeP systems) are a recently introduced neural-like model of computation. They provide an alternative to the more classical spiking neural (SN) P systems. In this paper, we present the first software simulator for DeP systems, and we investigate the key features of the representation of the syntax and semantics of such systems. First, the conceptual design of a simulation algorithm is discussed. This is helpful in order to shade a light on the differences with simulators for SN P systems, and also to identify potential parallelizable parts. Second, a novel simulator implemented within the PLingua simulation framework is presented. Moreover, MeCoSim, a GUI tool for abstract representation of problems based on P system models has been extended to support this model. An experimental validation of this simulator is also covered.

En el presente trabajo se realiza un análisis de los principales factores que afectan a la brecha digital como son la renta, el territorio, la preparación del centro educativo y las competencias digitales del profesorado y del alumnado. También se profundiza sobre las diferentes respuestas dadas durante la crisis de la COVID-19 por las diferentes administraciones, desde el nivel europeo hasta el nivel local. Se analiza la organización ante esta crisis de diferentes centros educativos de la ciudad de Sevilla que se encuentran en diversos contextos socioeconómicos. A través de un cuestionario dirigido a profesorado, se estudia el uso de las Tecnologías de la Información y la Comunicación (TIC), la opinión que tienen sobre éstas y cómo ha afectado la crisis sanitaria del coronavirus en el día a día de la docencia. Por último, se plantean diferentes propuestas para reducir la brecha digital en diferentes ámbitos como el legislativo, el organizativo y el curricular.

In 2005, Gh. Păun raised an interesting question concerning the role of electrical charges in P systems with active membranes from a complexity point of view. Specifically, he formulated a question about the computational efficiency of polarization-less P systems with dissolution rules and division rules only for elementary membranes. Several approaches have been carried out, and some partial answers have been given. This is probably the most important open problem in computational complexity theory in the framework of Membrane Computing. The study of the efficiency of membrane systems has been a very fruitful area, providing not only the above-stated partial answers, but also several frontiers of efficiency to tackle the P vs NP problem. In this work, a survey on classical and current results on complexity aspects is given, emphasizing on the frontiers of efficiency and the ingredients taken into account for each of them.

Motivated by the mechanism of inhibitory synapses, a new kind of spiking neural P (SNP) system rules, called inhibitory rules, is introduced in this paper. Based on this, a new variant of SNP systems is proposed, called spiking neural P systems with inhibitory rules (SNP-IR systems). Different from the usual firing rules in SNP systems, the firing condition of an inhibitory rule not only depends on the state of the neuron associated with the rule but also is related to the states of other neurons. Moreover, from the perspective of topological structure, the new variant is shown as a directed graph with inhibitory arcs, and therefore seems to have more powerful control. The computational completeness of SNPIR systems is discussed. In particular, it is proved that SNP-IR systems are Turing universal number accepting/generating devices. Moreover, we obtain a small universal function-computing device for SNP-IR systems consisting of 100 neurons.

It was recently found that dendrites are not just a passive channel. They can perform mixed computation of analog and digital signals, and therefore can be abstracted as information processors. Moreover, dendrites possess a feedback mechanism. Motivated by these computational and feedback characteristics, this article proposes a new variant of neural-like P systems, dendrite P (DeP) systems, where neurons simulate the computational function of dendrites and perform a firing–storing process instead of the storing–firing process in spiking neural P (SNP) systems. Moreover, the behavior of the neurons is characterized by dendrite rules that are abstracted by two characteristics of dendrites. Different from the usual firing rules in SNP systems, the firing of a dendrite rule is controlled by the states of the corresponding source neurons. Therefore, DeP systems can provide a collaborative control capability for neurons. We discuss the computational power of DeP systems. In particular, it is proven that DeP systems are Turing-universal number generating/accepting devices. Moreover, we construct a small universal DeP system consisting of 115 neurons for computing functions.

Psystems with active membranes is one of the most studied models within the field ofMembrane Computing. Simulating the organization and behavior of the living cells througha tree-like structure and abstracting the mechanisms that help the cell to keep alive intorules (evolution, communication, dissolution and division rules), they have been used tosolve several computationally hard problems. We are dealing with non-cooperative systemshere, that is, the number of reactives in a rule is always one. Even then, it has been proventhat problems from the classPSPACEcan be solved, so in order to acquire a minimal modelthat can solve computationally hard problems, polarizations are removed. In this paper wefind the relevance of the length of the right-hand side of the rule, being necessary whenusing separation rules and being irrelevant when division rules are used, improving somesolutions previously presented, restricting the right-hand side of the rules, obtaining newfrontiers of efficiency in this framework. The state of the art of these systems is presentedin a graphical way.

P-Lingua is a software framework for Membrane Computing, it includes a programming language, also called P-Lingua, for writting P system de nitions using a syntax close to standard scienti c notation. The rst line of a P-Lingua le is an unique identi er de ning the variant or model of P system to be used, i.e, the semantics of the P system. Software tools based on P-Lingua use this identi er to select a simulation algorithm implementing the corresponding derivation mode. Derivation modes de ne how to obtain a con guration Ct+1 from a con guration Ct. This information is usually hard-coded in the simulation algorithm. The P system model also de nes what types or rules can be used, the P-Lingua compiler uses the identi er to select an speci c parser for the le. In this case, a set of parsers is codi ed within the compiler tool. One for each unique identi er. P-Lingua has grown during the last 12 years, including more and more P system models. From a software engineering point of view, this approximation implies a continous development of the framework, leading to a monolithic software which is hard to debug and maintain. In this paper, we propose a new software approximation for the framework, including a new syntax for de ning rule patterns and derivation modes. The P-Lingua users can now de ne custom P system models instead of hard-coding them in the software. This approximation leads to a more exible solution which is easier to maintain and debug. Moreover, users could de ne and play with new/experimental P system models.

The search for effcient solutions of computationally hard problems by means of families of membrane systems has lead to a wide and prosperous eld of research. The study of computational complexity theory in Membrane Computing is mainly based on the look for frontiers of effciency between different classes of membrane systems. Every frontier provides a powerful tool for tackling the P versus NP problem in the following way. Given two classes of recognizer membrane systems R1 and R2, being systems from R1 non-effcient (that is, capable of solving only problems from the class P) and systems from R2 presumably e cient (that is, capable of solving NP-complete problems), and R2 the same class that R1 with some ingredients added, passing from R1 to R2 is comparable to passing from the non effciency to the presumed effciency. In order to prove that P = NP, it would be enough to, given a solution of an NP-complete problem by means of a family of recognizer membrane systems from R2, try to remove the added ingredients to R2 from R1. In this paper, we study if it is possible to solve SAT by means of a family of recognizer P systems from AM0(�����d;+n), whose non-effciency was demonstrated already.

La presente tesis se ha desarrollado en colaboración entre la Universidad de Sevilla y la Organización Europea para la Investigación Nuclear, CERN. El detector LHCb es uno de los cuatro grandes detectores situados en el Gran Colisionador de Hadrones, LHC. En LHCb, se colisionan partículas a altas energías para comprender la diferencia existente entre la materia y la antimateria. Debido a la cantidad ingente de datos generada por el detector, es necesario realizar un filtrado de datos en tiempo real, fundamentado en los conocimientos actuales recogidos en el Modelo Estándar de física de partículas. El filtrado, también conocido como High Level Trigger, deberá procesar un throughput de 40 Tb/s de datos, y realizar un filtrado de aproximadamente 1 000:1, reduciendo el throughput a unos 40 Gb/s de salida, que se almacenan para posterior análisis. El proceso del High Level Trigger se subdivide a su vez en dos etapas: High Level Trigger 1 (HLT1) y High Level Trigger 2 (HLT2). El HLT1 transcurre en tiempo real, y realiza una reducción de datos de aproximadamente 30:1. El HLT1 consiste en una serie de procesos software que reconstruyen lo que ha sucedido en la colisión de partículas. En la reconstrucción del HLT1 únicamente se analizan las trayectorias de las partículas producidas fruto de la colisión, en un problema conocido como reconstrucción de trazas, para dictaminar el interés de las colisiones. Por contra, el proceso HLT2 es más fino, requiriendo más tiempo en realizarse y reconstruyendo todos los subdetectores que componen LHCb. Hacia 2020, el detector LHCb, así como todos los componentes del sistema de adquisici´on de datos, serán actualizados acorde a los últimos desarrollos técnicos. Como parte del sistema de adquisición de datos, los servidores que procesan HLT1 y HLT2 también sufrirán una actualización. Al mismo tiempo, el acelerador LHC será también actualizado, de manera que la cantidad de datos generada en cada cruce de grupo de partículas aumentare en aprox, The current thesis has been developed in collaboration between Universidad de Sevilla and the European Organization for Nuclear Research, CERN. The LHCb detector is one of four big detectors placed alongside the Large Hadron Collider, LHC. In LHCb, particles are collided at high energies in order to understand the difference between matter and antimatter. Due to the massive quantity of data generated by the detector, it is necessary to filter data in real-time. The filtering, also known as High Level Trigger, processes a throughput of 40 Tb/s of data and performs a selection of approximately 1 000:1. The throughput is thus reduced to roughly 40 Gb/s of data output, which is then stored for posterior analysis. The High Level Trigger process is subdivided into two stages: High Level Trigger 1 (HLT1) and High Level Trigger 2 (HLT2). HLT1 occurs in real-time, and yields a reduction of data of approximately 30:1. HLT1 consists in a series of software processes that reconstruct particle collisions. The HLT1 reconstruction only analyzes the trajectories of particles produced at the collision, solving a problem known as track reconstruction, that determines whether the collision data is kept or discarded. In contrast, HLT2 is a finer process, which requires more time to execute and reconstructs all subdetectors composing LHCb. Towards 2020, the LHCb detector and all the components composing the data acquisition system will be upgraded. As part of the data acquisition system, the servers that process HLT1 and HLT2 will also be upgraded. In addition, the LHC accelerator will also be updated, increasing the data generated in every bunch crossing by roughly 5 times. Due to the accelerator and detector upgrades, the amount of data that the HLT will require to process is expected to increase by 40 times. The foreseen scalability of the software through 2020 underestimated the required resources to face the increase in data throughput. As a consequence, studies of all algorithms c

Pulse coupled neural networks (PCNN, for short) are models abstracting the synchronization behavior observed experimentally for the cortical neurons in the visual cortex of a cat’s brain, and the intersecting cortical model is a simplified version of the PCNN model. Membrane computing (MC) is a kind computation paradigm abstracted from the structure and functioning of biological cells that provide models working in cell-like mode, neural-like mode and tissue-like mode. Inspired from intersecting cortical model, this paper proposes a new kind of neural-like P systems, called dynamic threshold neural P systems (for short, DTNP systems). DTNP systems can be represented as a directed graph, where nodes are dynamic threshold neurons while arcs denote synaptic connections of these neurons. DTNP systems provide a kind of parallel computing models, they have two data units (feeding input unit and dynamic threshold unit) and the neuron firing mechanism is implemented by using a dynamic threshold mechanism. The Turing universality of DTNP systems as number accepting/generating devices is established. In addition, an universal DTNP system having 109 neurons for computing functions is constructed.

A single Turing machine can solve decision problems with an in nite number of instances. On the other hand, in the framework of membrane computing, a \solution" to an abstract decision problem consists of a family of membrane systems (where each system of the family is associated with a nite set of instances of the problem to be solved). An interesting question is to analyze the possibility to nd a single membrane system able to deal with the in nitely many instances of a decision problem. In this context, it is fundamental to de ne precisely how the instances of the problem are introduced into the system. In this paper, two different methods are considered: pre-computed (in polynomial time) resources and non-treated resources. An extended version of this work will be presented in the 20th International Conference on Membrane Computing.

The search for new mechanisms and tools allowing us to tackle the famousPversusNPproblem from new perspectives is an important task, due to the relevance of that problem.The concept of efficiency of computing models is associated with the ability to solveintractable (in a classical sense) problems in polynomial time. Assuming that P =NP, that concept is equivalent to the capability to solveNP-complete problems in an efficient way.Different frontiers of the efficiency have been given in Membrane Computing in terms ofsyntactical or semantic ingredients of the models. In particular, in the framework of tissueP systems with cell division using symport/antiport rules, the length of communicationrules (passing from length 1 to length 2) provides an optimal borderline of the efficiency. Cell-like P systems with symport/antiport rules and membrane division is a restrictedvariant of such tissue P systems in both its structure (rooted tree versus undirected graph)and in the way membranes communicate with each other and with the environment. Thelimitations of efficient computations in such kind of P systems which use non-cooperativecommunication rules have been previously established. In this paper, a uniform polynomialtime solution for the Hamiltonian cycle problem, a well knownNP-complete problem,by means of cell-like P systems with membrane division using minimal cooperation incommunication rules (at most two objects are involved), is provided. Hence, a new optimalboundary between tractability andNP-hardness, is provided: passing from non-cooperativerules to cooperative rules in cell-like P systems with symport/antiport rules and membranedivision amounts to passing from non-efficiency to efficiency.

The tape of a deterministic Turing machine contains an unbounded number of cells. Thanks to that, a single machine can solve decision problems with an infinite number of instances. Nevertheless, in the framework of membrane computing, traditionally a \solution" to an abstract decision problem consists of a family of membrane systems (where each system of the family is associated with a finite set of instances of the problem to be solved). An interesting question is to analyze the possibility to find a single membrane system able to deal with the infinitely many instances of a decision problem. In this context, it is fundamental to define precisely how the instances of the problem are introduced into the system. In this paper, two different methods are considered. The first one relies on a pre-computing process, where a polynomial-time computable function will be in charge of producing a multiset of objects associated with the instance to be solved. On the other hand, the second one assumes that the input alphabet of the system is equal to the alphabet of instances, and therefore instances are directly introduced in the initial configuration of the system. Polynomial complexity classes associated with these two approaches are introduced and some complexity aspects are studied.

In 2008, P-Lingua was born. The Research Group on Natural Computing worked on the development of simulation tools since the beginning of Membrane Computing. However, back in 2007, researchers from the group set out to the ambitious journey of creating a generic simulation framework for P systems. P-Lingua has evolved since then, o ering more exibility and a wider range of supported models. Many applications have also branched from this software project. In this paper, we brie y survey the evolution of P-Lingua to date, some of the associated applications, and prospective paths for upcoming challenges in the research area.

Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such membrane systems will be considered: (a) polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules; and (b) cell-like P systems with symport/antiport rules of minimal length. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two computing frameworks, in such manner that each borderline provides a tool to tackle the P versus NP problem.

The reconstruction of particle trajectories, tracking, is a central process in the reconstruction of particle collisions in High Energy Physics detectors. At the LHCb detector in the Large Hadron Collider, bunches of particles collide 30 million times per second. These collisions produce about 109 particle trajectories per second that need to be reconstructed in real time, in order to filter and store data. Upcoming improvements in the LHCb detector will deprecate the hardware filter in favour of a full software filter, posing a computing challenge that requires a renovation of current algorithms and the underlying hardware. We present Search by triplet, a local tracking algorithm optimized for parallel architectures. We design our algorithm reducing Read-After-Write dependencies as well as conditional branches, incrementing the potential for parallelization. We analyze the complexity of our algorithm and validate our results. We show the scaling of our algorithm for an increasing number of collision events. We show sustained tests for our algorithm sequence given a simulated dataflow. We develop CPU and GPU implementations of our work, and hide the transmission times between device and host by executing a multi-stream pipeline. Our results provide a reliable basis for an informed assessment on the feasibility of LHCb event reconstruction on parallel architectures, enabling us to develop cost models for upcoming technology upgrades. The created software infrastructure is extensible and permits the addition of subsequent reconstruction algorithms.