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. In: "13th International Conference on Membrane Computing", 28-31 May 2013, Budapest, Hungría. ISBN 978-963-311-372-1. pp. 390-403.

Description

Title: Limits of the power of Tissue P systems with cell division
Author/s:
  • Sosík, Petr
Item Type: Presentation at Congress or Conference (Article)
Event Title: 13th International Conference on Membrane Computing
Event Dates: 28-31 May 2013
Event Location: Budapest, Hungría
Title of Book: 13th International Conference on Membrane Computing
Date: 2013
ISBN: 978-963-311-372-1
Volume: 1
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (723kB)

Abstract

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

More information

Item ID: 26729
DC Identifier: http://oa.upm.es/26729/
OAI Identifier: oai:oa.upm.es:26729
Official URL: http://www.sztaki.hu/tcs/proba/cmc13/CMC13-proceedings.pdf
Deposited by: Memoria Investigacion
Deposited on: 18 Jun 2014 11:12
Last Modified: 22 Sep 2014 11:42
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM