Informática

URI permanente para esta comunidadhttps://hdl.handle.net/11441/33181

Examinar

Mostrando 1 - 20 de 22

A Characterization of PSPACE with Antimatter and Membrane Creation
(Fénix Editora, 2015) Gazdag, Zsolt; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
The use of negative information provides a new tool for exploring the limits of P systems as computational devices. In this paper we prove that the combination of antimatter and annihilation rules (based on the annihilation of physical particles and antiparticles) and membrane creation (based on autopoiesis) provides a P system model able to solve PSPACE-complete problems. Namely, we provide a uniform family of P system in such P system model which solves the satis ability problem for quanti ed Boolean formulas (QSAT). In the second part of the paper, we prove that all the decision problems which can be solved with this P system model belong to the complexity class PSPACE, so this P system model characterises PSPACE.
Antimatter as a Frontier of Tractability in Membrane Computing
(Fénix Editora, 2014) Díaz Pernil, Daniel; Peña Cantillana, Francisco; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural; Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada
It is well known that the polynomial complexity class of recognizer polarizationless P systems with active membranes, without dissolution and with division for elementary and non-elementary membranes is exactly the complexity class P (see [6], Th. 2). In this paper, we prove that if such P system model is endowed with antimatter and annihilation rules, then NP problems can be solved. In this way, antimatter is a frontier of tractability in Membrane Computing.
Application of Weighted Fuzzy Reasoning Spiking Neural P Systems to Fault Diagnosis in Traction Power Supply Systems of High-speed Railways
(Fénix Editora, 2014) Wang, Tao; Zhang, Gexiang; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
This paper discusses the application of weighted fuzzy reasoning spiking neu- ral P systems (WFRSN P systems) to fault diagnosis in traction power supply systems (TPSSs) of China high-speed railways. Four types of neurons are considered in WFRSN P systems to make them suitable for expressing status information of protective relays and circuit breakers, and a weighted matrix-based reasoning algorithm (WMBRA) is intro- duced to fulfill the reasoning based on the status information to obtain fault confidence levels of faulty sections. Fault diagnosis production rules in TPSSs and their WFRSN P system models are proposed to show how to use WFRSN P systems to describe different kinds of fault information. Building processes of fault diagnosis models for sections and fault region identification of feeding sections, and parameter setting of the models are described in detail. Case studies including normal power supply and over zone feeding show the effectiveness of the presented method.
Asynchronous Spiking Neural P Systems with Structural Plasticity
(Fénix Editora, 2015) Cabarle, Francis George C.; Adorna, Henry N.; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
Spiking neural P (in short, SNP) systems are computing devices inspired by biological spiking neurons. In this work we consider SNP systems with structural plasticity (in short, SNPSP systems) working in the asynchronous (in short, asyn mode). SNPSP systems represent a class of SNP systems that have dynamic synapses, i.e. neurons can use plasticity rules to create or remove synapses. We prove that for asyn mode, bounded SNPSP systems (where any neuron produces at most one spike each step) are not universal, while unbounded SNPSP systems with weighted synapses (a weight associated with each synapse allows a neuron to produce more than one spike each step) are universal. The latter systems are similar to SNP systems with extended rules in asyn mode (known to be universal) while the former are similar to SNP systems with standard rules only in asyn mode (conjectured not to be universal). Our results thus provide support to the conjecture of the still open problem.
Computational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation
(Fénix Editora, 2015) Valencia Cabrera, Luis; Song, Bosheng; Macías Ramos, Luis Felipe; Pan, Linqiang; Riscos Núñez, Agustín; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
Membrane ssion is a process by which a biological membrane is split into two new ones in such a way that the contents of the initial membrane is separated and distributed between the new membranes. Inspired by this biological phenomenon, membrane separation rules were considered in membrane computing. In this paper we deal with celllike P systems with membrane separation rules that use symport/antiport rules (such systems compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves) as communication rules. Speci cally we study a lower bound on the length of communication rules with respect to the computational e ciency of such kind of membrane systems; that is, their ability to solve computationally hard problems in polynomial time by trading space for time. The main result of this paper is the following: communication rules involving at most three objects is enough to achieve the computational e ciency of P systems with membrane separation. Thus, a polynomial time solution to SAT problem is provided in this computing framework. It is known that only problems in P can be solved in polynomial time by using minimal cooperation in communication rules and membrane separation, so the lower bound of the e ciency obtained is an optimal bound.
FORMA 15 : Complex Systems Workshop: Sevilla 25-28 Noviembre 2015
(Fidetia, 2016) Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Miguel Rodríguez, Jaime de; Borrego Díaz, Joaquín; Sancho Caparrini, Fernando; Aranda Corral, Gonzalo A.; Domínguez Sánchez de la Blanca, Ismael; Ministerio de Economía y Competitividad (MINECO). España
Kernel P Systems - Version 1
(Fénix Editora, 2013) Gheorgue, Marian; Ipate, Florentin; Dragomir, Ciprian; Mierla, Laurentiu; Valencia Cabrera, Luis; García Quismondo, Manuel; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Junta de Andalucía; Universidad de Sevilla. TIC193: Computación Natural
A basic P system, called kernel P system4 (kP system for short), combining features of di erent P systems introduced and studied so far is de ned and discussed. The structure of such systems is de ned as a dynamic graph, similar to tissue-like P systems, the objects are organised as multisets, and the rules in each compartment, rewriting and communication together with system structure changing rules, are applied in accordance with a speci c execution strategy. The de nition of kP systems is introduced and some examples illustrate this concept. Two classes of P systems, namely neural-like and generalised communicating P systems are simulated by kP systems. Some case studies prove the expressive power of these systems.
Limits on P Systems with Proteins and Without Division
(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Orellana Martín, David; Valencia Cabrera, Luis; Riscos Núñez, Agustín; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; National Natural Science Foundation of China; Universidad de Sevilla. TIC193: Computación Natural
In the field of Membrane Computing, computational complexity theory has been widely studied trying to nd frontiers of efficiency by means of syntactic or semantical ingredients. The objective of this is to nd two kinds of systems, one non-efficient and another one, at least, presumably efficient, that is, that can solve NP-complete prob- lems in polynomial time, and adapt a solution of such a problem in the former. If it is possible, then P = NP. Several borderlines have been defi ned, and new characterizations of different types of membrane systems have been published. In this work, a certain type of P system, where proteins act as a supporting element for a rule to be red, is studied. In particular, while division rules, the abstraction of cellular mitosis is forbidden, only problems from class P can be solved, in contrast to the result obtained allowing them.
Minimal Cooperation in P Systems with Symport/Antiport: A Complexity Approach
(Fénix Editora, 2015) Valencia Cabrera, Luis; Song, Bosheng; Macías Ramos, Luis Felipe; Pan, Linqiang; Riscos Núñez, Agustín; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
Membrane systems with symport/antiport rules compute by just moving objects among membranes, and not by changing the objects themselves. In these systems the environment plays an active role because, not only it receives objects from the system, but it also sends objects into the system. Actually, in this framework it is commonly assumed that an arbitrarily large number of copies of some objects are initially available in the environment. This special feature has been widely exploited for the design of e cient solutions to computationally hard problems in the framework of tissue like P systems able to create an exponential workspace in polynomial time (e.g. via cell division or cell separation rules). This paper deals with cell-like P systems which use symport/antiport rules as communication rules, and the role played by the minimal cooperation is studied from a computational complexity point of view. Speci cally, the limitations on the e ciency of P systems with membrane separation whose symport/antiport rules involve at most two objects are established. In addition, a polynomial time solution to HAM-CYCLE problem, a well known NP-complete problem, by using a family of such kind of P systems with membrane division, is provided. Therefore, in the framework of cell-like P systems with minimal cooperation in communication rules, passing from membrane separation to membrane division amounts to passing from tractability to NP{hardness.
Narrowing Frontiers of Efficiency with Evolutional Communication Rules and Cell Separation
(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Orellana Martín, David; Valencia Cabrera, Luis; Song, Bosheng; Pan, Linqiang; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; National Natural Science Foundation of China; Universidad de Sevilla. TIC193: Computación Natural
In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important way to tackle the P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumably efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the SAT problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the right-hand side of the rules have at most two objects.
Notes on Spiking Neural P Systems and Finite Automata
(Fénix Editora, 2015) Cabarle, Francis George C.; Adorna, Henry N.; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
Spiking neural P systems (in short, SNP systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SNP systems with standard rules have neurons that emit at most one spike (the pulse) each step, and have either an input or output neuron connected to the environment. SNP transducers were introduced, where both input and output neurons were used. More recently, SNP modules were introduced which generalize SNP transducers: extended rules are used (more than one spike can be emitted each step) and a set of input and output neurons can be used. In this work we continue relating SNP modules and nite automata: (i) we amend previous constructions for DFA and DFST simulations, (ii) improve the construction from three neurons down to one neuron, (iii) DFA with output are simulated, and (iv) we generate automatic sequences using results from.
On The Semantics of Annihilation Rules in Membrane Computing
(Fénix Editora, 2015) Díaz Pernil, Daniel; Freund, Rudolf; Gutiérrez Naranjo, Miguel Ángel; Leporati, Alberto; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural; Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada
It is well known that polarizationless recognizer P systems with active membranes, without dissolution, with division of elementary and non-elementary membranes, with antimatter and matter/antimatter annihilation rules can solve all problems in NP when the annihilation rules have (weak) priority over all the other rules. Until now, it was an open problem whether these systems can still solve all NP problems if the priority of the matter/antimatter annihilation rules is removed. In this paper we provide a negative answer to this question: we prove that the class of problems solvable by this model of P systems without priority of the matter/antimatter annihilation rules is exactly P. To the best of our knowledge, this is the rst paper in the literature of P systems where the semantics of applying the rules constitutes a frontier of tractability.
Parallel Simulation of PDP Systems: Updates and Roadmap
(Fénix Editora, 2015) Martínez del Amor, Miguel Ángel; Macías Ramos, Luis Felipe; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
PDP systems are a type of multienvironment P systems, which serve as a formal modeling framework for Population Dynamics. The accurate simulation of these probabilistic models entails large run times. Hence, parallel platforms such as GPUs has been employed to speedup the simulation. In 2012 [14], the rst GPU simulator of PDP systems was presented. In this paper, we present current updates made on this simulator, and future developments to consider.
Probabilistic Guarded P Systems, A Formal Definition
(Fénix Editora, 2014) García Quismondo, Manuel; Martínez del Amor, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Junta de Andalucía; Universidad de Sevilla. TIC193: Computación Natural
In this paper, we extend the general framework of Multienvironment P systems, which is a formal framework for modelling the dynamics of population biology. The extension is made by a new variant within the probabilistic approach, called Probabilistic Guarded P systems (in short, PGP systems).We provide a formal de nition, a simulation algorithm to capture the dynamics, and a survey of the associated software.
Rete Algorithm for P System Simulators
(Fénix Editora, 2013) Graciani Díaz, Carmen; Gutiérrez Naranjo, Miguel Ángel; Riscos Núñez, Agustín; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Junta de Andalucía; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
The Rete algorithm is a well-known algorithm in rule-based production systems which builds directed acyclic graphs that represent higher-level rule sets. This allows the rule-based systems to avoid complete re-evaluation of all conditions of the rules each step in order to check the applicability of the rules and, therefore, the computational e ciency of the production systems is improved. In this paper we study how these ideas can be applied in the improvement of the design of computational simulators in the framework of Membrane Computing.
Revisiting Sevilla Carpets: A New Tool for the P-Lingua Era
(Fénix Editora, 2014) Orellana Martín, David; Graciani Díaz, Carmen; Martínez del Amor, Miguel Ángel; Riscos Núñez, Agustín; Valencia Cabrera, Luis; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
Sevilla Carpets have already been used to compare di erent solutions of the Subset Sum problem: either designed in the framework of P systems with active membranes (both in the case of membrane division and membrane creation), and also another one in the framework of tissue-like P systems with cell division. Recently, the degree of parallelism and other descriptive complexity details have been found to be relevant when designing parallel simulators running on GPUs. We present here a new way to use the information provided by Sevilla carpets, and a script that allows to generate them automatically from P-Lingua les.
Self-constructing Recognizer P Systems
(Fénix Editora, 2014) Díaz Pernil, Daniel; Peña Cantillana, Francisco; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural; Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada
Usually, the changes produced in the membrane structure of a P system are considered side effects. The output of the computation is encoded as a multiset placed in a specific region and the membrane structure in the halting configuration is not considered important. In this paper we explore P systems where the target of the computation is the construction of a new membrane structure according its set of rules. The new membrane structure can be considered as the initial one of a new self-constructed P system. We focus on the self-construction of recognizer P systems and illustrates the definition with a study of the self-construction P systems working as decision trees for solving Machine Learning decision problems.
Simulating a Family of Tissue P Systems Solving SAT on the GPU
(Fénix Editora, 2013) Martínez del Amor, Miguel Ángel; Pérez Carrasco, Jesús; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Junta de Andalucía; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
In order to provide e cient software tools to deal with large membrane systems, high-throughput simulators are required. Parallel computing platforms are good candidates, since they are capable of partially implementing the inherently parallel nature of the model. In this concern, today GPUs (Graphics Processing Unit) are considered as highly parallel processors, and they are being consolidated as accelerators for scienti c applications. In fact, previous attempts to design P systems simulators on GPUs have shown that a parallel architecture is better suited in performance than traditional single CPUs. In 2010, a GPU-based simulator was introduced for a family of P systems with active membranes solving SAT in linear time. This is the starting point of this paper, which presents a new GPU simulator for another polynomial-time solution to SAT by means of tissue P systems with cell division, trading space for time. The aim of this simulator is to further study which ingredients of di erent P systems models are well suited to be managed by the GPU.
Solving SAT with Antimatter in Membrane Computing
(Fénix Editora, 2015) Díaz Pernil, Daniel; Alhazov, Artiom; Freund, Rudolf; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural; Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada
The set of NP-complete problems is split into weakly and strongly NP- complete ones. The di erence consists in the in uence of the encoding scheme of the input. In the case of weakly NP-complete problems, the intractability depends on the encoding scheme, whereas in the case of strongly NP-complete problems the problem is intractable even if all data are encoded in a unary way. The reference for strongly NP-complete problems is the Satis ability Problem (the SAT problem). In this paper, we provide a uniform family of P systems with active membranes which solves SAT { without polarizations, without dissolution, with division for elementary membranes and with matter/antimatter annihilation. To the best of our knowledge, it is the rst solution to a strongly NP-complete problem in this P system model.
Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques
(Fénix Editora, 2014) Gazdag, Zsolt; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; Universidad de Sevilla. TIC193: Computación Natural
In Membrane Computing, the solution of a decision problem X belonging to the complexity class P via a polynomially uniform family of recognizer P systems is trivial, since the polynomial encoding of the input can involve the solution of the problem. The design of such solution has one membrane, two objects, two rules and one computation step. Stricto sensu, it is a solution in the framework of Membrane Computing, but it does not use Membrane Computing strategies. In this paper, we present three designs of uniform families of P systems that solve the decision problem STCON by using Membrane Computing strategies (pure Membrane Computing techniques): P systems with membrane creation, P systems with active membranes with dissolution and without polarizations and P systems with active membranes without dissolution and with polarizations. Since STCON is NL-complete, such designs are constructive proofs of the belonging of NL to PMCMC, PMCAM0 +d and PMCAM+

Examinar

Examinando Informática por Agencia financiadora "Ministerio de Economía y Competitividad (MINECO). España"