Revistes Publicacions URV: Triangle - llenguatge, literatura, computació> 2011

Minimal Parallelism and Number of Membrane Polarizations

  • Datos identificativos

    Identificador: RP:4419
    Handle: https://hdl.handle.net/20.500.11797/RP4419
    Autores:
    Alhazov, Artiom
    Resumen:
    It is known that the satisfiability problem (SAT) can be efficiently solved by a uniform family of P systems with active membranes that have two polarizations working in a maximally parallel way. We study P systems with active membranes without non-elementary membrane division, working in minimally parallel way. The main question we address is what number of polarizations is sufficient for an efficient computation depending on the types of rules used. In particular, we show that it is enough to have four polarizations, sequential evolution rules changing polarizations, polarizationless non-elementary membrane division rules and polarizationless rules of sending an object out. The same problem is solved with the standard evolution rules, rules of sending an object out and polarizationless non-elementary membrane division rules, with six polarizations. It is an open question whether these numbers are optimal.

  • Otros:

    Autor según el artículo: Alhazov, Artiom
    Palabras clave: language
    Resumen: It is known that the satisfiability problem (SAT) can be efficiently solved by a uniform family of P systems with active membranes that have two polarizations working in a maximally parallel way. We study P systems with active membranes without non-elementary membrane division, working in minimally parallel way. The main question we address is what number of polarizations is sufficient for an efficient computation depending on the types of rules used. In particular, we show that it is enough to have four polarizations, sequential evolution rules changing polarizations, polarizationless non-elementary membrane division rules and polarizationless rules of sending an object out. The same problem is solved with the standard evolution rules, rules of sending an object out and polarizationless non-elementary membrane division rules, with six polarizations. It is an open question whether these numbers are optimal.
    Año de publicación de la revista: 2011
    Tipo de publicación: info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article