Logo del repository
  1. Home
 
Opzioni

The counting power of P systems with antimatter

Leporati Alberto
•
Manzoni Luca
•
Mauri Giancarlo
altro
Zandron Claudio
2017
  • journal article

Periodico
THEORETICAL COMPUTER SCIENCE
Abstract
We give a characterisation of the class of problems solved in polynomial time by uniform and semi-uniform families of P systems with active membranes, using matter/antimatter annihilation rules and elementary membrane division. Like several other variants of P systems with elementary division, this class is exactly P^#P, that is, the problems solvable efficiently with access to oracles for counting problems. We also consider the monodirectional case, where objects in the P system can only move from inner regions towards outer regions. In that case, the above model of P systems characterises the class P_∥^#P, where each query is independent of the result of the others; this contrasts with traditional P systems with active membranes, which characterise the (conjecturally proper) subclass P_∥^NP.
DOI
10.1016/j.tcs.2017.03.045
WOS
WOS:000418969500016
Archivio
http://hdl.handle.net/11368/2947798
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85017509077
https://www.sciencedirect.com/science/article/pii/S0304397517302840
Diritti
closed access
license:copyright editore
FVG url
https://arts.units.it/request-item?handle=11368/2947798
Soggetti
  • Computational complex...

  • Membrane computing

  • P systems with active...

  • P systems with antima...

Web of Science© citazioni
9
Data di acquisizione
Mar 20, 2024
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