Repositorio de producción científica de la Universidad de Sevilla

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


Advanced Search

Show simple item record

dc.creator Murphy, Niall
dc.creator Woods, Damien 2016-03-22T08:53:40Z 2016-03-22T08:53:40Z 2009
dc.identifier.isbn 9788461328369 es
dc.description.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. es
dc.format application/pdf es
dc.language.iso eng es
dc.publisher Fénix Editora es
dc.relation.ispartof Proceedings of the Seventh Brainstorming Week on Membrane Computing, vol.II, 73-84. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2009 es
dc.rights Attribution-NonCommercial-NoDerivatives 4.0 Internacional *
dc.rights.uri *
dc.title The Computational Complexity of Uniformity and Semi-uniformity in Membrane Systems es
dc.type info:eu-repo/semantics/conferenceObject es
dc.type.version info:eu-repo/semantics/publishedVersion es
dc.rights.accessrights info:eu-repo/semantics/openAccess
Size: 211.4Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record