BWMC2019: Brainstorming Week on Menbrane Computing (17th. 2019. Sevilla)

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

Examinar

Mostrando 1 - 14 de 14

Seventeenth Brainstorming Week on Membrane Computing Sevilla, February 5 - 8, 2019 : RGNC REPORT 1/2019
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Orellana Martín, David; Paun, Gheorghe; Riscos Núñez, Agustín; Andreu Guzmán, José A.; 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
The DBSCAN Clustering Algorithm on P Systems
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Vaszil, György; Research Group on Natural Computing
We show how to implement the DBSCAN clustering algorithm (Density Based Spatial Clustering of Applications with Noise) on membrane systems using evolution rules with promoters and priorities.
New applications for an old tool
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Valencia Cabrera, Luis; Orellana Martín, David; Pérez Hurtado de Mendoza, Ignacio; Pérez Jiménez, Mario de Jesús; 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
First, the dependency graph technique, not so far from its current application, was developed trying to nd the shortest computations for membrane systems solving instances of SAT. Certain families of membrane systems have been demonstrated to be non-effcient by means of the reduction of nding an accepting computation (respectively, rejecting computation) to the problem of reaching from a node of the dependency graph to another one. In this paper, a novel application to this technique is explained. Supposing that a problem can be solved by means of a kind of membrane systems leads to a contradiction by means of using the dependency graph as a reasoning method. In this case, it is demonstrated that a single system without dissolution, polarizations and cooperation cannot distinguish a single object from more than one object. An extended version of this work will be presented in the 20th International Conference on Membrane Computing.
Search Based Software Engineering in Membrane Computing
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Turlea, Ana; Gheorghe, Marian; Ipate, Florentin; Research Group on Natural Computing
This paper presents a testing approach for kernel P Systems (kP systems), based on test data generation for a given scenario. This method uses Genetic Algorithms to generate the input sets needed to trigger the given computation steps.
A syntax for semantics in P-Lingua
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Pérez Hurtado de Mendoza, Ignacio; Orellana Martín, David; 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; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación Natural
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.
An apparently innocent problem in Membrane Computing
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) 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; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación Natural
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.
A new perspective on computational complexity theory in Membrane Computing
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) 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; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación Natural
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.
Simulating counting oracles with cooperation
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio; Research Group on Natural Computing
We prove that monodirectional shallow chargeless P systems with active membranes and minimal cooperation working in polynomial time precisely characterise P#P k , the complexity class of problems solved in polynomial time by deterministic Turing machines with a polynomial number of parallel queries to an oracle for a counting problem.
Playing with Derivation Modes and Halting Conditions
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Freund, Rudolf; Research Group on Natural Computing
In the area of P systems, besides the standard maximally parallel derivation mode, many other derivation modes have been investigated, too. In this paper, many variants of hierarchical P systems and tissue P systems using different derivation modes are considered and the effects of using di erent derivation modes, especially the maximally parallel derivation modes and the maximally parallel set derivation modes, on the generative and accepting power are illustrated. Moreover, an overview on some control mechanisms used for (tissue) P systems is given. Furthermore, besides the standard total halting mode, we also consider different halting conditions such as unconditional halting and partial halting and explain how the use of different halting modes may considerably change the computing power of P systems and tissue P systems.
Further Results on the Power of Generating APCol Systems
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Ciencialová, Lucie; Cienciala, Ludek; Csuhaj-Varjú, Erzsébet; Research Group on Natural Computing
In this paper we continue our investigations in APCol systems (Automatonlike P colonies), variants of P colonies where the environment of the agents is given by a string and the functioning of the system resembles to the functioning of standard nite automaton. We rst deal with the concept of determinism in these systems and compare deterministic APCol systems with deterministic register machines. Then we focus on generating non-deterministic APCol systems with only one agent. We show that these systems are as powerful as 0-type grammars, i.e., generate any recursively enumerable language. If the APCol system is non-erasing, then any context-sensitive language can be generated by a non-deterministic APCol systems with only one agent.
Membrane Systems with Priority, Dissolution, Promoters and Inhibitors and Time Petri Nets
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Battyányi, Péter; Vaszil, György; Research Group on Natural Computing
We continue the investigations on exploring the connection between membrane systems and time Petri nets already commenced in [4] by extending membrane systems with promoters/inhibitors, membrane dissolution and priority for rules compared to the simple symbol-object membrane system. By constructing the simulating Petri net, we retain one of the main characteristics of the Petri net model, namely, the firings of the transitions can take place in any order: we do not impose any additional stipulation on the transition sequences in order to obtain a Petri net model equivalent to the general Turing machine. Instead, we substantially exploit the gain in computational strength obtained by the introduction of the timing feature for Petri nets.
P Systems: from Anti-Matter to Anti-Rules
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu; Pérez Jiménez, Mario de Jesús; 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
The concept of a matter object being annihilated when meeting its corresponding anti-matter object is taken over for rule labels as objects and anti-rule labels as the corresponding annihilation counterpart in P systems. In the presence of a corresponding anti-rule object, annihilation of a rule object happens before the rule that the rule object represents, can be applied. Applying a rule consumes the corresponding rule object, but may also produce new rule objects as well as anti-rule objects, too. Computational completeness in this setting then can be obtained in a one-membrane P system with non-cooperative rules and rule / anti-rule annihilation rules when using one of the standard maximally parallel derivation modes as well as any of the maximally parallel set derivation modes (i.e., non-extendable (multi)sets of rules, (multi)sets with maximal number of rules, (multi)sets of rules a ecting the maximal number of objects). When using the sequential derivation mode, at least the computational power of partially blind register machines is obtained.
(Tissue) P Systems with Anti-Membranes
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu; Research Group on Natural Computing
The concept of a matter object being annihilated when meeting its corresponding anti-matter object is taken over for membranes as objects and anti-membranes as the corresponding annihilation counterpart in P systems. Natural numbers can be represented by the corresponding number of membranes with a speci c label. Computational completeness in this setting then can be obtained with using only elementary membrane division rules, without using objects. A similar result can be obtained for tissue P systems with cell division rules and cell / anti-cell annihilation rules. In both cases, as derivation modes we may take the standard maximally parallel derivation modes as well as any of the maximally parallel set derivation modes (non-extendable (multi)sets of rules, (multi)sets with maximal number of rules, (multi)sets of rules a ecting the maximal number of objects).
Beyond Generalized Multiplicities: Register Machines over Groups
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu; Research Group on Natural Computing
Register machines are a classic model of computing, often seen as a canonical example of a device manipulating natural numbers. In this paper, we de ne register machines operating on general groups instead. This generalization follows the research direction started in multiple previous works. We study the expressive power of register machines as a function of the underlying groups, as well as of allowed ingredients (zero test, partial blindness, forbidden regions). We put forward a fundamental connection between register machines and vector addition systems. Finally, we show how registers over free groups can be used to store and manipulate strings.

Examinar

Envíos recientes