MURAL - Maynooth University Research Archive Library

    Membrane dissolution and division in P

    Woods, Damien and Murphy, Niall and Pérez-Jiménez, Mario J. and Riscos-Núñez, Agustín (2009) Membrane dissolution and division in P. In: Unconventional Computation, Proceedings of the 8th International Conference, UC 2009, Ponta Delgada, Portugal. Springer, Berlin, pp. 262-276. ISBN 9783642037443

    [img] Download (236kB)

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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 dierent contents, we show that their power is upperbounded by P.

    Item Type: Book Section
    Additional Information: This work is supported by a Project of Excellence TIC-581 from the Junta de Andalucía, project TIN 2006 13425 of the Ministerio de Educación y Ciencia of Spain, and the Irish Research Council for Science, Engineering and Technology. We thank the anonymous reviewers for helpful comments on the presentation.
    Keywords: Membrane dissolution; membrane division; PSPACE problems;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 2504
    Depositing User: CS Editor
    Date Deposited: 20 Apr 2011 15:38
    Publisher: Springer
    Refereed: No
    Funders: Junta de Andalucía, Ministerio de Educación y Ciencia of Spain, Irish Research Council for Science, Engineering and Technology
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads