Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Membrane Dissolution and Division in P

Damien Woods21, Niall Murphy22, Mario J. Pérez-Jiménez21 and Agustín Riscos-Núñez21

(21)  Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Seville, Spain
(22)  Department of Computer Science, National University of Ireland Maynooth, Ireland
Abstract
Membrane systems with dividing and dissolving membranes are known to solve PSPACE problems in polynomial time. However, we give a P upperbound on an important restriction of such systems. In particular we examine systems with dissolution, elementary division and where each membrane initially has at most one child membrane. Even though such systems may create exponentially many membranes, each with different contents, we show that their power is upperbounded by P.
This work is supported by a Project of Excellence TIC-581 from the Junta de Andalucía, project TIN 2006 13425 of Ministerio de Educación y Ciencia of Spain, and the Irish Research Council for Science, Engineering and Technology.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)