Computing with cells: membrane systems - some complexity issues.

Ibarra, Oscar H. y Paun, Andrei Paul (2008). Computing with cells: membrane systems - some complexity issues.. "International Journal of Parallel Emergent and Distributed Systems", v. 23 (n. 5); pp. 347-365. ISSN 1744-5760. https://doi.org/10.1080/17445760701640266.

Descripción

Título: Computing with cells: membrane systems - some complexity issues.
Autor/es:
  • Ibarra, Oscar H.
  • Paun, Andrei Paul
Tipo de Documento: Artículo
Título de Revista/Publicación: International Journal of Parallel Emergent and Distributed Systems
Fecha: Octubre 2008
Volumen: 23
Materias:
Palabras Clave Informales: membrane system; symport/antiport system; catalytic system; contextsensitive language.
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (771kB) | Vista Previa

Resumen

Membrane computing is a branch of natural computing which abstracts computing models from the structure and the functioning of the living cell. The main ingredients of membrane systems, called P systems, are (i) the membrane structure, which consists of a hierarchical arrangements of membranes which delimit compartments where (ii) multisets of symbols, called objects, evolve according to (iii) sets of rules which are localised and associated with compartments. By using the rules in a nondeterministic/deterministic maximally parallel manner, transitions between the system configurations can be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from one membrane to another and applying the rules, as well as possibilities to dissolve, divide or create membranes have been studied. Membrane systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems once future biotechnology gives way to a practical bio-realization. In this paper we survey some interesting and fundamental complexity issues such as universality vs. nonuniversality, determinism vs. nondeterminism, membrane and alphabet size hierarchies, characterizations of context-sensitive languages and other language classes and various notions of parallelism.

Más información

ID de Registro: 2260
Identificador DC: http://oa.upm.es/2260/
Identificador OAI: oai:oa.upm.es:2260
Identificador DOI: 10.1080/17445760701640266
URL Oficial: http://www.informaworld.com/smpp/content~db=all?content=10.1080/17445760701640266
Depositado por: Memoria Investigacion
Depositado el: 12 Feb 2010 12:00
Ultima Modificación: 20 Abr 2016 12:01
  • InvestigaM
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM