Mostrar el registro sencillo del ítem
Ponencia
Computational Complexity of Simple P Systems
dc.creator | Ciobanu, Gabriel | |
dc.creator | Resios, Andreas | |
dc.date.accessioned | 2016-03-17T10:03:21Z | |
dc.date.available | 2016-03-17T10:03:21Z | |
dc.date.issued | 2008 | |
dc.identifier.isbn | 9788461244294 | es |
dc.identifier.uri | http://hdl.handle.net/11441/38701 | |
dc.description.abstract | We introduce a new class of membrane systems called simple P systems, and study its computational complexity using the classical theory. We start by presenting the knapsack problem and analyzing its space and time complexities. Then we study the computational complexity of simple P systems by considering the static allocation of resources enabling the parallel application of the rules. We show that the problem of allocating resources for simple P systems is NP-complete by reducing it to the knapsack problem. Thus we express the computational complexity of this class of P systems in terms of classical complexity theory. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix Editora | es |
dc.relation.ispartof | Proceedings of the Sixth Brainstorming Week on Membrane Computing, 107-121. Sevilla, E.T.S. de Ingeniería Informática, 4-8 de Febrero, 2008 | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Computational Complexity of Simple P Systems | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/38701 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
gabriel.pdf | 210.4Kb | [PDF] | Ver/ | |