Logo del repository
  1. Home
 
Opzioni

Evaluating space measures in P systems

Alhazov, A
•
Leporati, A
•
Manzoni, L
altro
Zandron, C
2022
  • journal article

Periodico
JOURNAL OF MEMBRANE COMPUTING
Abstract
P systems with active membranes are a variant of P systems where membranes can be created by division of existing membranes, thus creating an exponential amount of resources in a polynomial number of steps. Time and space complexity classes for active membrane systems have been introduced, to characterize classes of problems that can be solved by different membrane systems making use of different resources. In particular, space complexity classes introduced initially considered a hypothetical real implementation by means of biochemical materials, assuming that every single object or membrane requires some constant physical space (corresponding to unary notation). A different approach considered implementation of P systems in silico, allowing to store the multiplicity of each object in each membrane using binary numbers. In both cases, the elements contributing to the definition of the space required by a system (namely, the total number of membranes, the total number of objects, the types of different membranes, and the types of different objects) was considered as a whole. In this paper, we consider a different definition for space complexity classes in the framework of P systems, where each of the previous elements is considered independently. We review the principal results related to the solution of different computationally hard problems presented in the literature, highlighting the requirement of every single resource in each solution. A discussion concerning possible alternative solutions requiring different resources is presented.
DOI
10.1007/s41965-022-00106-5
WOS
WOS:000865376300001
Archivio
https://hdl.handle.net/11368/3037665
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85139490741
https://link.springer.com/article/10.1007/s41965-022-00106-5
Diritti
open access
license:creative commons
license uri:http://creativecommons.org/licenses/by/4.0/
FVG url
https://arts.units.it/bitstream/11368/3037665/2/s41965-022-00106-5.pdf
Soggetti
  • Membrane system

  • Computational complex...

  • Space complexity

google-scholar
Get Involved!
  • Source Code
  • Documentation
  • Slack Channel
Make it your own

DSpace-CRIS can be extensively configured to meet your needs. Decide which information need to be collected and available with fine-grained security. Start updating the theme to match your nstitution's web identity.

Need professional help?

The original creators of DSpace-CRIS at 4Science can take your project to the next level, get in touch!

Realizzato con Software DSpace-CRIS - Estensione mantenuta e ottimizzata da 4Science

  • Impostazioni dei cookie
  • Informativa sulla privacy
  • Accordo con l'utente finale
  • Invia il tuo Feedback