dc.creator | Pérez Hurtado de Mendoza, Ignacio | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.creator | Gutiérrez Naranjo, Miguel Ángel | es |
dc.creator | Rius Font, Miquel | es |
dc.date.accessioned | 2024-04-22T10:55:42Z | |
dc.date.available | 2024-04-22T10:55:42Z | |
dc.date.issued | 2011 | |
dc.identifier.citation | Pérez Hurtado de Mendoza, I., Pérez Jiménez, M.d.J., Riscos Núñez, A., Gutiérrez Naranjo, M.Á. y Rius Font, M. (2011). On a partial affirmative answer for a Paun's Conjecture. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22 (1), 55-64. https://doi.org/10.1142/S0129054111007824. | |
dc.identifier.issn | 1793-6373 | es |
dc.identifier.uri | https://hdl.handle.net/11441/156952 | |
dc.description.abstract | At the beginning of 2005, Gheorghe Pun formulated a conjecture stating that in the framework of recognizer P systems with active membranes (evolution rules, communication rules, dissolution rules and division rules for elementary membranes), polarizations cannot be avoided in order to solve computationally hard problems efficiently (assuming that P ≠ NP). At the middle of 2005, a partial positive answer was given, proving that the conjecture holds if dissolution rules are forbidden. In this paper we give a detailed and complete proof of this result modifying slightly the notion of dependency graph associated with recognizer P systems. | es |
dc.format | application/pdf | es |
dc.format.extent | 9 | es |
dc.language.iso | eng | es |
dc.publisher | WORLD SCIENTIFIC PUBL CO PTE LTD | es |
dc.relation.ispartof | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22 (1), 55-64. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Active membranes | es |
dc.subject | Computational complexity | es |
dc.subject | Dissolution rules | es |
dc.subject | Polarizationless P systems | es |
dc.subject | Tractability | es |
dc.title | On a partial affirmative answer for a Paun's Conjecture | es |
dc.type | info:eu-repo/semantics/article | es |
dc.type.version | info:eu-repo/semantics/acceptedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.identifier.doi | 10.1142/S0129054111007824 | es |
dc.journaltitle | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | es |
dc.publication.volumen | 22 | es |
dc.publication.issue | 1 | es |
dc.publication.initialPage | 55 | es |
dc.publication.endPage | 64 | es |