Limits of the power of Tissue P systems with cell division

Sosík, Petr (2013). Limits of the power of Tissue P systems with cell division. En: "13th International Conference on Membrane Computing", 28-31 May 2013, Budapest, Hungría. ISBN 978-963-311-372-1. pp. 390-403.

Descripción

Título: Limits of the power of Tissue P systems with cell division
Autor/es:
  • Sosík, Petr
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 13th International Conference on Membrane Computing
Fechas del Evento: 28-31 May 2013
Lugar del Evento: Budapest, Hungría
Título del Libro: 13th International Conference on Membrane Computing
Fecha: 2013
ISBN: 978-963-311-372-1
Volumen: 1
Materias:
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 (723kB)

Resumen

Tissue P systems generalize the membrane structure tree usual in original models of P systems to an arbitrary graph. Basic opera- tions in these systems are communication rules, enriched in some variants with cell division or cell separation. Several variants of tissue P systems were recently studied, together with the concept of uniform families of these systems. Their computational power was shown to range between P and NP ? co-NP , thus characterizing some interesting borderlines between tractability and intractability. In this paper we show that com- putational power of these uniform families in polynomial time is limited by the class PSPACE . This class characterizes the power of many clas- sical parallel computing models

Más información

ID de Registro: 26729
Identificador DC: http://oa.upm.es/26729/
Identificador OAI: oai:oa.upm.es:26729
URL Oficial: http://www.sztaki.hu/tcs/proba/cmc13/CMC13-proceedings.pdf
Depositado por: Memoria Investigacion
Depositado el: 18 Jun 2014 11:12
Ultima Modificación: 22 Sep 2014 11:42
  • 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
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM