|
Gheorghe PAUN, Mario J. PEREZ-JIMENEZ
Henry ADORNA, Gheorghe PAUN, Mario J. PEREZ-JIMENEZ Abstract. Abstract. Looking for a theory of communication complexity for P systems, we consider here so-called evolution-communication (EC for short) P systems, where objects evolve by multiset rewriting rules without target commands and pass through membranes by means of symport/antiport rules. We first propose a way to measure the communication costs by means of “quanta of energy” (produced by evolution rules and) consumed by communication rules. EC P systems with such costs are proved to be Turing complete in all three cases with respect to the relation between evolution and communication operations: priority of communication, mixing the rules without priority for any type, priority of evolution (with the cost of communication increasing in this ordering in the universality proofs).
Hepzibah A. CHRISTINAL, Daniel DIAZ-PERNIL, Miguel A. GUTIERREZ-NARANJO, Mario J. PEREZ-JIMENEZ Abstract. Thresholding is the process of splitting a digital image into sets of pixels in order to make it easier to analyze. Pixels are ordered according to a scale of one of their features as brightness or color and the final image is obtained by comparing the measure of the feature with some thresholds. In this paper we present a family of cell-like P systems which solve the thresholding problem in linear time on the number of pixels. Read the pdf
Daniel DIAZ-PERNIL, Miguel A. GUTIERREZ-NARANJO, Pedro REAL, Vanesa SANCHEZ-CANALES Abstract. We present a new solution for the Homology Groups of Binary 2D Image (HGB2I) Problem by using Membrane Computing techniques. This is a classical problem in Homology Theory which tries to calculate the number of connected components and the representative curves of the holes of these components from a given binary 2D image. To this aim, we present a family of P systems which solves all the instances of the problem in the framework of Tissue-like P systems with catalysts. This is a new framework which combines the membrane structure and symport-antiport communication rules of tissue-like P systems with the power of catalysts. Read the pdf
Raluca LEFTICARU, Florentin IPATE, Marian GHEORGHE Abstract. 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 has been developed and used for test case generation. Some hints regarding the automatic test generation using NuSMV and P-Lingua are also given. Read the pdf.
Alberto LEPORATI, Claudio FERRETTI Abstract. We propose to use tissue-like P systems as a tool to model and analyse the security properties of firewall 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. Read the pdf.
Adam OBTULOWICZ Abstract. 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.
Antonio E. PORRECA, Alberto LEPORATI, Giancarlo MAURI, Claudio ZANDRON Abstract. 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.
Dragos SBURLAN Abstract. 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 (IFT). In particular, we focus on a variant of catalytic P systems which satisfies in addition to the original definition the following property: if in a region of the P system an object is the subject of a catalytic rule, then in the same region it must exists also a non-cooperative rule that rewrites the same object. Finally, we also give a normal form for catalytic P systems. Read the pdf.
|