Show simple item record

Presentation

dc.creatorAdorna, Henry N.
dc.creatorPaun, Gheorghe
dc.creatorPérez Jiménez, Mario de Jesús
dc.date.accessioned2016-03-28T07:18:48Z
dc.date.available2016-03-28T07:18:48Z
dc.date.issued2010
dc.identifier.isbn978-84-614-2357-6es
dc.identifier.urihttp://hdl.handle.net/11441/38983
dc.description.abstractLooking for a theory of communication complexity for P systems, we consider here so-called evolution-communication (EC for short) P systems, where objects evolve by multiset rewriting rules without target commands and pass through membranes by means of symport/antiport rules. (Actually, in most cases below we use only symport rules.) We first propose a way to measure the communication costs by means of “quanta of energy” (produced by evolution rules and) consumed by communication rules. EC P systems with such costs are proved to be Turing complete in all three cases with respect to the relation between evolution and communication operations: priority of communication, mixing the rules without priority for any type, priority of evolution (with the cost of communication increasing in this ordering in the universality proofs). More appropriate measures of communication complexity are then defined, as dynamical parameters, counting the communication steps or the number (and the weight) of communication rules used during a computation. Such parameters can be used in three ways: as properties of P systems (considering the families of sets of numbers generated by systems with a given communication complexity), as conditions to be imposed on computations (accepting only those computations with a communication complexity bounded by a given threshold), and as standard complexity measures (defining the class of problems which can be solved by P systems with a bounded complexity). Because we ignore the evolution steps, in all three cases it makes sense to consider hierarchies starting with finite complexity thresholds. We only give some preliminary results about these hierarchies (for instance, proving that already their lower levels contain complex – e.g., non-semilinear – sets), and we leave open many problems and research issues.es
dc.description.sponsorshipJunta de Andalucía P08 – TIC 04200
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherFénix Editoraes
dc.relation.ispartofProceedings of the Eighth Brainstorming Week on Membrane Computing, 1-21. Sevilla, E.T.S. de Ingeniería Informática, 1-5 de Febrero, 2010es
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleOn Communication Complexity in Evolution-Communication P Systemses
dc.typeinfo:eu-repo/semantics/conferenceObjectes
dcterms.identifierhttps://ror.org/03yxnpp24
dc.type.versioninfo:eu-repo/semantics/publishedVersiones
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificiales
dc.relation.projectIDP08 – TIC 04200
dc.contributor.groupUniversidad de Sevilla. TIC193: Computación Natural
dc.identifier.idushttps://idus.us.es/xmlui/handle/11441/38983
dc.contributor.funderJunta de Andalucía

FilesSizeFormatViewDescription
01commcomplexity.pdf230.2KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional