Ponencia
The Computational Power of Exponential-Space P Systems with Active Membranes
Autor/es | Alhazov, Artiom
Leporati, Alberto Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Fecha de publicación | 2012 |
Fecha de depósito | 2016-02-03 |
Publicado en |
|
ISBN/ISSN | 978-84-940056-5-7 |
Resumen | We show that exponential-space P systems with active membranes characterize
the complexity class EXPSPACE. This result is proved by simulating Turing
machines working in exponential space via uniform families of P systems ... We show that exponential-space P systems with active membranes characterize the complexity class EXPSPACE. This result is proved by simulating Turing machines working in exponential space via uniform families of P systems with restricted elementary active membranes; the simulation is e cient, in the sense that the time and space required are at most polynomial with respect to the resources employed by the simulated Turing machine. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
artiom2.pdf | 483.9Kb | [PDF] | Ver/ | |