dc.creator | Alhazov, Artiom | es |
dc.creator | Freund, Rudolf | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.date.accessioned | 2019-03-29T11:36:28Z | |
dc.date.available | 2019-03-29T11:36:28Z | |
dc.date.issued | 2006 | |
dc.identifier.citation | Alhazov, A., Freund, R. y Riscos Núñez, A. (2006). Membrane division, restricted membrane creation and object complexity in P systems. International Journal of Computer Mathematics, 83 (7), 529-547. | |
dc.identifier.issn | 0020-7160 | es |
dc.identifier.uri | https://hdl.handle.net/11441/84929 | |
dc.description.abstract | We improve, by using register machines, some existing universality results for specific models of
P systems. P systems with membrane creation are known to generate all recursively enumerable sets
of vectors of non-negative integers, even when no region (except the environment) contains more than
one object of the same kind.We showhere that they generate all recursively enumerable languages, and
that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable
vectors of non-negative integers). Moreover, at most two objects are present inside the system at any
time in the generative case.We then prove that 10 + msymbols are sufficient to generate any recursively
enumerable language over m symbols. P systems with active membranes without polarizations are
known to generate all recursively enumerable sets of vectors of non-negative integers. We show that
they generate all recursively enumerable languages; four starting membranes with three labels or
seven starting membranes with two labels are sufficient. P systems with active membranes and two
polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative
integers, using only rules of rewriting and sending objects out.We show that accepting can be done by
deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly
created membrane can only be of the same kind as the parent one) generate at least matrix languages,
even when having at most one object in the configuration (except the environment). We conclude by
presenting a summary of the main results obtained in this paper and a list of open questions. | es |
dc.description.sponsorship | Ministerio de Ciencia y Tecnología TIC2002-04220-C03-01 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Taylor and Francis | es |
dc.relation.ispartof | International Journal of Computer Mathematics, 83 (7), 529-547. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Membrane division | es |
dc.subject | Restricted membrane creation | es |
dc.subject | Object complexity | es |
dc.subject | P systems | es |
dc.title | Membrane division, restricted membrane creation and object complexity in P systems | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | 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.relation.projectID | TIC2002-04220-C03-01 | es |
dc.relation.publisherversion | https://www.tandfonline.com/doi/abs/10.1080/00207160601065314 | es |
dc.identifier.doi | 10.1080/00207160601065314 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 19 | es |
dc.journaltitle | International Journal of Computer Mathematics | es |
dc.publication.volumen | 83 | es |
dc.publication.issue | 7 | es |
dc.publication.initialPage | 529 | es |
dc.publication.endPage | 547 | es |
dc.identifier.sisius | 6701502 | es |