BWMC2010. Brainstorming Week On Membrane Computing (8th. 2010. Sevilla)

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

Examinar

Mostrando 1 - 20 de 27

Eighth Brainstorming Week on Membrane Computing, Sevilla, February 1-5, 2010 : RGNC REPORT 1/2010
(Fénix Editora, 2010) Martínez del Amor, Miguel Ángel; Paun, Gheorghe; Pérez Hurtado de Mendoza, Ignacio; Riscos Núñez, Agustín; 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
An Approximate Algorithm Combining P Systems and Ant Colony Optimization for Traveling Salesman Problems
(Fénix Editora, 2010) Zhang, Gexiang; Cheng, Jixiang; Gheorghe, Marian
This paper proposes an approximate optimization algorithm combining P systems with ant colony optimization, called ACOPS, to solve traveling salesman prob- lems, which are well-known and extensively studied NP-complete combinatorial optimization problems. ACOPS uses the pheromone model and pheromone update rules defined by ant colony optimization algorithms, and the hierarchical membrane structure and transformation/communication rules of P systems. First, the parameter setting of the ACOPS is discussed. Second, extensive experiments and statistical analysis are investigated. It is shown that the ACOPS is superior to Nishida's algorithms and its counterpart ant colony optimization algorithms, in terms of the quality of solutions and the number of function evaluations.
When Matrices Meet Brains
(Fénix Editora, 2010) Zeng, Xiangxiang; Adorna, Henry N.; Martínez del Amor, Miguel Ángel; Pan, Linqiang; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. In this work, a discrete structure representation of SN P systems is proposed. Specifically, matrices are used to represent SN P systems. In order to represent the computations of SN P systems by matrices, configuration vectors are defined to monitor the number of spikes in each neuron at any given configuration; transition net gain vectors are also introduced to quantify the total amount of spikes consumed and produced after the chosen rules are applied. Nondeterminism of the systems is assured by a set of spiking transition vectors that could be used at any given time during the computation. With such matrix representation, it is quite convenient to determine the next configuration from a given configuration, since it involves only multiplying vectors to a matrix and adding vectors.
Standardized Proofs of PSPACE-completeness of P Systems with Active Membranes
(Fénix Editora, 2010) Sosík, Petr; Rodríguez Patón, Alfonso; Ciencialová, Lucie
Two proofs have been shown for P systems with active membranes in previ- ously published papers, demonstrating that these P systems can solve in polynomial time exactly the class of problems PSPACE. Consequently, these P systems are equivalent (up to a polynomial time reduction) to Second Machine Class models as the alternating Turing machine or the PRAM computer. These proofs were based on a modified definition of uniform families of P systems. Here we demonstrate that the results remain valid also in the case of standard definitions.
"Dogmatic" P Systems
(Fénix Editora, 2010) Sempere, José M.
In this work we propose a variant of P systems based on the Central Dogma of Molecular Biology which establishes the transformation of DNA strands into protein products by applying different string transformation such as transductions and transcriptions. We introduce a new kind of worm object rules to carry out transducion operations. Finally, we establish the universality of the proposed model by simulating Iterated finite state sequential transducers (IFTs).
On Catalytic P Systems with One Catalyst
(Fénix Editora, 2010) Sburlan, Dragos
In this paper we address the possibility of studying the computational capabilities of catalytic P systems with one catalyst by the means of iterated finite state transducers. We also give a normal form for catalytic P systems.
On Complexity Classes of Spiking Neural P Systems
(Fénix Editora, 2010) Rodríguez Patón, Alfonso; Sosík, Petr; Cienciala, Ludek
A sequence of papers have been recently published, pointing out various intractable problems which may be solved in certain fashions within the framework of spiking neural (SN) P systems. On the other hand, there are also results demonstrating limitations of SN P systems. In this paper we define recognizer SN P systems providing a general platform for this type of results. We intend to give a more systematic characterization of computational power of variants of SN P systems, and establish their relation to standard complexity classes.
First Steps Towards Linking Membrane Depth and the Polynomial Hierarchy
(Fénix Editora, 2010) Porreca, Antonio E.; Murphy, Niall
In this paper we take the first steps in studying possible connections between non-elementary division with limited membrane depth and the levels of the Polynomial Hierarchy. We present a uniform family with a membrane structure of depth d + 1 that solves a problem complete for level d of the Polynomial Hierarchy.
Complete Problems for a Variant of P Systems with Active Membranes
(Fénix Editora, 2010) Porreca, Antonio E.; Leporati, Alberto; Mauri, Giancarlo; Zandron, Claudio
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 highlight some possible connections with open problems related to the computational complexity of P systems with active membranes.
Dynamics of Randomly Constructed Computational Systems
(Fénix Editora, 2010) Peña, Miguel A.; Frisco, Pierluigi
We studied Petri nets with five places constructed in a pseudo-random way: their underlying net is composed of join and fork. We report initial results linking the dynamical properties of these systems to the topology of their underlying net. The obtained results can be easily related to the computational power of some abstract models of computation.
Solving Problems in a Distributed Way in Membrane Computing: dP Systems
(Fénix Editora, 2010) Paun, Gheorghe; 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; Universidad de Sevilla. TIC193: Computación Natural
Although P systems are distributed parallel computing devices, no explicit way of handling the input in a distributed way in this framework was considered so far. This note proposes a distributed architecture (based on cell-like P systems, with their skin membranes communicating through channels as in tissue-like P systems, according to specified rules of the antiport type), where parts of a problem can be introduced as inputs in various components and then processed in parallel. The respective devices are called dP systems, with the case of accepting strings called dP automata. The communication complexity can be evaluated in various ways: statically (counting the communication rules in a dP system which solves a given problem), or dynamically (counting the number of communication steps, of communication rules used in a computation, or the number of objects communicated). For each measure, two notions of “parallelizability” can be introduced. Besides (informal) definitions, some illustrations of these idea are provided for dP automata: each regular language is “weakly parallelizable” (i.e., it can be recognized in this framework, using a constant number of communication steps), and there are languages of various types with respect to Chomsky hierarchy which are “efficiently parallelizable” (they are parallelizable and, moreover, are accepted in a faster way by a dP automaton than by a single P automaton). Several suggestions for further research are made.
Linking Bistable Dynamics to Metabolic P Systems
(Fénix Editora, 2010) Pagliarini, Roberto; Bianco, Luca; Manca, Vincenzo; Bessant, Conrad
Bistability, or more generally multistability, is an important recurring theme in biological systems. In particular, the discovery of bistability in signal pathways of genetic networks, prompts strong interest in understanding both the design and function of these networks. Therefore, modelling these systems is crucial to understand their behaviors, and also to analyze and identify characteristics that would otherwise be di cult to realize. Although di erent classes of models have been used to study bistable dynamics, there is a lag in the development of models for bistable systems starting from experimental data. This is due to the lack of detailed knowledge of biochemical reactions and kinetic rates. In this work, we propose a procedure to develop, starting from observed dynamics, Metabolic P models for multistable processes. As a case study, a mathematical model of the Schl ogel's dynamics, which represents an example of a chemical reaction system that exhibits bistability, is inferred starting from observed stochastic bistable dynamics. Since, recent experiments indicate that noise plays an important role in the switching of bistable systems, the success of this work suggests that this approach is a very promising one for studying dynamics and role of noise in biological systems, such as, for example, genetic regulatory networks.
Gandy-Paun-Rozenberg Machines
(Fénix Editora, 2010) Obtulowicz, Adam
Gandy-Paun-Rozenberg machines are introduced as certain graph rewriting systems. A representation of Gandy-Paun-Rozenberg machines by Gandy machines is given. A construction of a Gandy-Paun-Rozenberg machine solving 3-SAT problem in a polynomial time is shown.
Modeling and Analysis of Firewalls by (Tissue-like) P Systems
(Fénix Editora, 2010) Leporati, Alberto; Ferretti, Claudio
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 packet filters, routers and firewalls gives the possibility to check - and possibly mathematically prove - some security properties.
Model Checking Based Test Generation from P Systems Using P-Lingua
(Fénix Editora, 2010) Lefticaru, Raluca; Ipate, Florentin; Gheorgue, Marian
This paper presents an approach for P system testing, that uses model- checking for automatic test generation and P-Lingua as specification language. This approach is based on a transformation of the transitional, non-deterministic, cell-like P system into a Kripke structure, which is further used for test generation, by adding convenient temporal logic specifications. This paper extends our previous work in this field to multi-membrane, transitional P system, having cooperative rules, communication between membranes and membrane dissolution. A tool, which takes as input a P system specified in P-Lingua and translates it into the language accepted by the model checker NuSMV was developed and used for test case generation. Some hints regarding the automatic test generation using NuSMV and P-Lingua are also given.
Plain Talk about Systems Complicatedness
(Fénix Editora, 2010) Kelemen, Jozef
Membrane Computing Meets Artificial Intelligence: A Case Study
(Fénix Editora, 2010) Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
The usual way to find a solution for a NP complete problem with Membrane Computing techniques is by brute force algorithms where all the feasible solutions are generated and they are checked simultaneously by using massive parallelism. These solutions work from a theoretical point of view but they are implementable only for small instances of the problem. In this paper we provide a family of P systems which brings techniques from Artificial Intelligence into Membrane Computing and apply them to solve the N-queens problem.
How Does a P System Sound?
(Fénix Editora, 2010) García Quismondo, Manuel; Gutiérrez Naranjo, Miguel Ángel; Ramírez Martínez, Daniel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
P systems are computational devices versatile enough to represent many real-life scenarios. In this paper, we present a first interpretation for P systems where a computation produces a set of sounds. The idea is to associate sounds to the application of specific rules in the P system. The application of such rules produces sounds of one time unit. Different rules produce different sounds. The combination of such sounds along time can be interpreted as music.
Applying Membrane Systems in Food Engineering
(Fénix Editora, 2010) Escuela, Gabi; Hinze, Thomas; Dittrich, Peter; Schuster, Stefan; Moreno Álvarez, Mario
Food engineering deals with manufacturing, packaging and distributing systems for drug and food products. In this work, we discuss about the applicability of membrane systems to model environmental conditions and their e ects on the produces during storage of fresh fruits and vegetables. In particular, we are interested in abstract molecular interactions that occur between produce, lm and surrounding atmosphere factors involved in fresh fruit and vegetable package designs. We present a basic implementation to simulate the dynamical behaviour of these systems, due to gas exchanges and temperature uctuations. Additionally, we reveal the bene ts of this modelling approach and suggest some extensions as future directions to be considered.
An Application of Genetic Algorithms to Membrane Computing
(Fénix Editora, 2010) Escuela, Gabi; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
The process of designing a P system in order to perform a task is a hard job. The researcher has often only an approximate idea of the design, but finding the exact description of the rules is a heavy hand-made work. In this paper we introduce PSystemEvolver, an evolutionary algorithm based on generative encoding, that could help to design a P system to perform a specific task. We illustrate the use of PSystemEvolver with a simple mathematical problem: the computation of squared numbers.

Examinar

Envíos recientes