Alternative Space Definitions for P Systems with Active Membranes
Închide
Articolul precedent
Articolul urmator
357 0
SM ISO690:2012
ALHAZOV, Artiom, LEPORATI, Alberto, MANZONI, Luca, MAURI, Giancarlo, ZANDRON, Claudio. Alternative Space Definitions for P Systems with Active Membranes. In: Brainstorming Week On Membrane Computing, 4-7 februarie 2020, Sevilla. Sevilla, Spania: Universidad de Sevilla, 2020, Ediția a 18-a, pp. 9-20.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Brainstorming Week On Membrane Computing
Ediția a 18-a, 2020
Masa rotundă "Eighteenth Brainstorming Week On Membrane Computing"
Sevilla, Spania, 4-7 februarie 2020

Alternative Space Definitions for P Systems with Active Membranes


Pag. 9-20

Alhazov Artiom1, Leporati Alberto2, Manzoni Luca3, Mauri Giancarlo2, Zandron Claudio2
 
1 Vladimir Andrunachievici Institute of Mathematics and Computer Science,
2 University of Milano-Bicocca,
3 University of Trieste
 
 
Disponibil în IBN: 8 mai 2021


Rezumat

The first definition of space complexity for P systems was based on an hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A different approach can also be considered, having in mind an implementation of P systems in silico; in this case, the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space.

Cuvinte-cheie
Membrane Systems, computational complexity, Space Complexity