BWMC2018: Brainstorming Week on Membrane Computing (16th. 2018. Sevilla)
URI permanente para esta colecciónhttps://hdl.handle.net/11441/82506
Examinar
Envíos recientes
Ponencia 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 NaturalIn 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.Ponencia 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 NaturalIn 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.Ponencia Characterizing PSPACE with Shallow Non-Confluent P Systems(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, ClaudioIn P systems with active membranes, the question of understanding the power of non-confluence within a polynomial time bound is still an open problem. It is known that, for shallow P systems, that is, with only one level of nesting, non-con uence allows them to solve conjecturally harder problems than con uent P systems, thus reaching PSPACE. Here we show that PSPACE is not only a bound, but actually an exact characterization. Therefore, the power endowed by non-con uence to shallow P systems is equal to the power gained by con uent P systems when non-elementary membrane division and polynomial depth are allowed, thus suggesting a connection between the roles of non-confluence and nesting depth.Ponencia Spiking Neural P Systems with Addition/Subtraction Computing on Synapses(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Jiang, Yun; Chen, ZhiqiangSpiking neural P systems (SN P systems, for short) are a class of distributed and parallel computing models inspired from biological spiking neurons. In this paper, we introduce a variant called SN P systems with addition/subtraction computing on synapses (CSSN P systems). CSSN P systems are inspired and motivated by the shunting inhibition of biological synapses, while incorporating ideas from dynamic graphs and networks. We consider addition and subtraction operations on synapses, and prove that CSSN P systems are computationally universal as number generators, under a normal form (i.e. a simplifying set of restrictions).Ponencia Testing Identifiable Kernel P Systems Using an X-machine Approach(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Gheorghe, Marian; Ipate, Florentin; Lefticaru, Raluca; Turlea, AnaThis paper presents a testing approach for kernel P systems (kP systems), based on the X-machine testing framework and the concept of cover automaton. The testing methodology ensures that the implementation conforms the speci cations, under certain conditions, such as the identi ably concept in the context of kernel P systems.Ponencia P Colony Automata with LL(k)-like Conditions(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Csuhaj Varjú, Erzsébet; Kántor, Kristóf; Vaszil, GyörgyWe investigate the possibility of the deterministic parsing (that is, parsing without backtracking) of languages characterized by (generalized) P colony automata. We de ne a class of P colony automata satisfying a property which resembles the LL(k) property of context-free grammars, and study the possibility of parsing the characterized languages using a k symbol lookahead, as in the LL(k) parsing method for context-free languages.Ponencia A Note on a New Class of APCol Systems(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Ciencialová, Lucie; Csuhaj Varjú, Erzsébet; Vaszil, GyörgyWe introduce a new acceptance mode for APCol systems (Automaton-like P colonies), variants of P colonies where the environment of the agents is given by a string and during functioning the agents change their own states and process the string similarly to automata. In case of the standard variant, the string is accepted if it can be reduced to the empty word. In this paper, we de ne APCol systems where the agents verify their environment, a model resembling multihead nite automata. In this case, a string of length n is accepted if during every halting computation the length of the environmental string in the con gurations does not change and in the course of the computation every agent applies a rule to a symbol on position i of some of the environmental strings for every i, 1 < i < n at least once. We show that these verifying APCol systems simulate one-way multihead nite automata.Ponencia Input-Driven Tissue P Automata(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu; Oswald, Marion; Verlan, SergeyWe introduce several variants of input-driven tissue P automata where the rules to be applied only depend on the input symbol. Both strings and multisets are considered as input objects; the strings are either read from an input tape or defined by the sequence of symbols taken in, and the multisets are given in an input cell at the beginning of a computation, enclosed in a vesicle. Additional symbols generated during a computation are stored in this vesicle, too. An input is accepted when the vesicle reaches a final cell and it is empty. The computational power of some variants of input-driven tissue P automata is illustrated by examples and compared with the power of the input-driven variants of other automata as register machines and counter automata.Ponencia One-Membrane P Systems with Activation and Blocking of Rules(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Alhazov, Artiom; Freund, Rudolf; Ivanov, SergiuWe introduce new possibilities to control the application of rules based on the preceding applications, which can be de ned in a general way for (hierarchical) P systems and the main known derivation modes. Computational completeness can be obtained even for one-membrane P systems with non-cooperative rules and using both activation and blocking of rules, especially for the set modes of derivation. When we allow the application of rules to in uence the application of rules in previous derivation steps, applying a non-conservative semantics for what we consider to be a derivation step, we can even \go beyond Turing".Ponencia Introducing the Concept of Activation and Blocking of Rules in the General Framework for Regulated Rewriting in Sequential Grammars(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Alhazov, Artiom; Freund, Rudolf; Ivanov, SergiuWe introduce new possibilities to control the application of rules based on the preceding application of rules which can be de ned for a general model of sequential grammars and we show some similarities to other control mechanisms as graph-controlled grammars and matrix grammars with and without applicability checking as well as gram- mars with random context conditions and ordered grammars. Using both activation and blocking of rules, in the string and in the multiset case we can show computational com- pleteness of context-free grammars equipped with the control mechanism of activation and blocking of rules even when using only two nonterminal symbols.