MURAL - Maynooth University Research Archive Library



    The Computational Complexity of Uniformity and Semi-uniformity in Membrane Systems


    Murphy, Niall and Woods, Damien (2009) The Computational Complexity of Uniformity and Semi-uniformity in Membrane Systems. In: Seventh Brainstorming Week on Membrane Computing, 2 – 6 February 2009, Seville. (Unpublished)

    [thumbnail of NM_Computational_Complexity.pdf] PDF
    NM_Computational_Complexity.pdf

    Download (193kB)

    Abstract

    We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples include circuits, membrane systems, DNA computers, cellular automata, tile assembly systems, and so on. However, in this list there are actually two distinct kinds of uniformity conditions. The first is the most common and well-understood, where each input length is mapped to a single computing device that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input. The former notion is well-known and used in circuit complexity, while the latter notion is frequently found in literature on nature-inspired computing models, from the past 20 years or so. Are these two notions distinct or not? For many models it has been found that these notion are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. Here, we buck this trend and show that these notions are actually distinct: we give classes of uniform membrane systems that are strictly weaker than their semi-uniform counterparts. This solves a known open problem in the theory of membrane systems.
    Item Type: Conference or Workshop Item (Paper)
    Additional Information: Niall Murphy is funded by the Irish Research Council for Science, Engineering and Technology. Damien Woods is supported by a Project of Excellence from the Junta de Andaluca, grant number TIC-581.
    Keywords: Computational Complexity; Uniformity; Semi-uniformity; Membrane Systems;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 2497
    Depositing User: CS Editor
    Date Deposited: 13 Apr 2011 15:49
    Refereed: No
    Funders: Irish Research Council for Science, Engineering and Technology
    URI: https://mural.maynoothuniversity.ie/id/eprint/2497
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads