Computing with membranes: P systems with worm-objects
Authors:
- G. PaunGPG. Paun
- A. Rodriguez-PatonARA. Rodriguez-Paton
- 7 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 65-74
Abstract
We consider a combination of P systems with objects described by symbols with P systems with objects described by strings. Namely, we work with multisets of strings and consider as the result of a computation the number of strings in a given output membrane. The strings (also called worms) are processed by replication, splitting, mutation, and recombination; no priority among rules and no other ingredient is used. In these circumstances, it is proved that: (1) P systems of this type can generate all recursively enumerable sets of numbers; and moreover, (2) the Hamiltonian Path Problem in a directed graph can be solved in quadratic time, while the SAT problem can be solved in linear time. The interest of the latter result comes from the fact that it is the first time that a polynomial solution to an NP-complete problem has been obtained in the P system framework without making use of the (non-realistic) operation of membrane division.Keywords
This publication has 12 references indexed in Scilit:
- COMPUTING WITH MEMBRANES (P SYSTEMS): A VARIANTInternational Journal of Foundations of Computer Science, 2000
- DNA Computing1998
- Handbook of Formal Languages1997
- DNA Solution of Hard Computational ProblemsScience, 1995
- Molecular Computation of Solutions to Combinatorial ProblemsScience, 1994
- Studying Artificial Life Using a Simple, General Cellular ModelArtificial Life, 1994
- Petri net algorithms in the theory of matrix grammarsActa Informatica, 1994
- Regulated Rewriting in Formal Language Theory1989
- Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviorsBulletin of Mathematical Biology, 1987
- On finite monoids having only trivial subgroupsInformation and Control, 1965