BWMC2015. Brainstorming Week on Membrane Computing (13th. 2015. Sevilla)

URI permanente para esta colecciónhttps://hdl.handle.net/11441/33343

Examinar

Mostrando 1 - 20 de 21

Some Quick Research Topics
(Fénix Editora, 2015) Paun, Gheorghe
Some research topics are suggested, in a preliminary form, in most cases dealing with (somewhat nonstandard) extensions of existing types of P systems.
Thirteen Brainstorming Week on Membrane Computing Sevilla, February 2-6, 2015 : RGNC Report 1/2015
(Fénix Editora, 2015) Macías Ramos, Luis Felipe; Paun, Gheorghe; Riscos Núñez, Agustín; Valencia Cabrera, Luis; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación Natural
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.
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.
Looking for Computers in the Biological Cell. After Twenty Years
(Fénix Editora, 2015) Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
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.
Monodirectional P Systems
(Fénix Editora, 2015) Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio
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" are, when working in polynomial time and under standard complexity-theoretic assumptions, much less powerful than unrestricted ones: indeed, they characterise classes of problems de ned by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space.
The Pole Balancing Problem with Enzymatic Numerical P Systems
(Fénix Editora, 2015) Llorente Rivera, Domingo; 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
Pole balancing is a control benchmark widely used in engineering. It involves a pole a xed to a cart via a joint which allows movement along a single axis. In this problem, the movement of the cart is restricted to the horizontal axis by a track and the pole is free to move about the horizontal axis of the pivot. The system is extremely unstable and, the cart must be in constant movement in order to preserve the equilibrium and avoid the fall of the pendulum. In this paper, we study the pole balancing problem in the framework of Enzymatic Numerical P Systems and provide some clues for using them in more complex systems.
kPWorkbench: A Software Framework for Kernel P Systems
(Fénix Editora, 2015) Gheorgue, Marian; Ipate, Florentin; Mierla, Laurentiu; Konur, Savas
P systems are the computational models introduced in the context of membrane computing, a computational paradigm within the more general area of unconventional computing. Kernel P (kP) systems are de ned to unify the speci cation of di erent variants of P systems, motivated by challenging theoretical aspects and the need to model di erent problems. In this paper, we present kPWorkbench, a software framework developed to support kP systems. kPWorkbench integrates several simula- tion and veri cation tools and methods, and provides a software suit for the modelling and analysis of membrane systems.
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.
How to Go Beyond Turing with P Automata: Time Travels, Regular Observer !-Languages, and Partial Adult Halting
(Fénix Editora, 2015) Freund, Rudolf; Ivanov, Sergiu; Staiger, Ludwig
In this paper we investigate several variants of P automata having in nite runs on nite inputs. By imposing speci c conditions on the in nite evolution of the systems, it is easy to nd ways for going beyond Turing if we are watching the behavior of the systems on in nite runs. As speci c variants we introduce a new halting variant for P automata which we call partial adult halting with the meaning that a speci c prede ned part of the P automaton does not change any more from some moment on during the in nite run. In a more general way, we can assign !-languages as observer languages to the in nite runs of a P automaton. Speci c variants of regular !-languages then, for example, characterize the red-green P automata.
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.
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.
Automaton-like P Colonies
(Fénix Editora, 2015) Cienciala, Ludek; Ciencialová, Lucie; Csuhaj Varjú, Erzsébet
In this paper we study P colonies where the environment is given as a string. These variants, called automaton-like P systems or APCol systems, behave like automata: during functioning, the agents change their own states and process the symbols of the string. We develop the concept of APCol systems by introducing the notion of their generating working mode. We then compare the power of APCol systems working in the generating mode and that of register machines and context-free matrix grammars with and without appearance checking.
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.
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.
Simulating Membrane Systems and Dissolution in a Typed Chemical Calculus
(Fénix Editora, 2015) Aman, Bogdan; Battyányi, Péter; Ciobanu, Gabriel; Vaszil, György
We present a transformation of membrane systems, possibly with pro- moter/inhibitor rules, priority relations, and membrane dissolution, into formulas of the chemical calculus such that terminating computations of membranes correspond to terminating reduction sequences of formulas and vice versa. In the end, the same result can be extracted from the underlying computation of the membrane system as from the reduction sequence of the chemical term. The simulation takes place in a typed chemical calculus, but we also give a short account of the untyped case.
Extended Spiking Neural P Systems with White Hole Rules
(Fénix Editora, 2015) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu; Oswald, Marion; Verlan, Sergey
We consider extended spiking neural P systems with the additional possibility of so-called \white hole rules", which send the complete contents of a neuron to other neurons, and we show how this extension of the original model allow for easy proofs of the computational completeness of this variant of extended spiking neural P systems using only one actor neuron. Using only such white hole rules, we can easily simulate special variants of Lindenmayer systems.
Variants of P Systems with Toxic Objects
(Fénix Editora, 2015) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu
Toxic objects have been introduced to avoid trap rules, especially in (purely) catalytic P systems. No toxic object is allowed to stay idle during a valid derivation in a P system with toxic objects. In this paper we consider special variants of toxic P systems where the set of toxic objects is prede ned { either by requiring all objects to be toxic or all catalysts to be toxic or all objects except the catalysts to be toxic. With all objects staying inside and being toxic, purely catalytic P systems cannot go beyond the nite sets, neither as generating nor as accepting systems. With allowing the output to be sent to the environment, exactly the regular sets can be generated. With non-cooperative systems with all objects being toxic we can generate exactly the Parikh sets of languages generated by extended Lindenmayer systems. Catalytic P systems with all catalysts being toxic can generate at least PsMAT.
Polarizationless P Systems with One Active Membrane
(Fénix Editora, 2015) Alhazov, Artiom; Freund, Rudolf
The aim of this paper is to study the computational power of P systems with one active membrane without polarizations. For P systems with active membranes, it is known that computational completeness can be obtained with either of the following combinations of features: 1)two polarizations, 2)membrane creation and dissolution, 3)four membranes with three labels, membrane division and dissolution, 4)seven membranes with two labels, membrane division and dissolution. Clearly, with one membrane only object evolution rules and send-out rules are permitted. Two variants are considered: external output and internal output.

Examinar

Envíos recientes