Limits of the power of tissue P systems with cell division

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F13%3A%230004811" target="_blank" >RIV/47813059:19240/13:#0004811 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Limits of the power of tissue P systems with cell division

Original language description

Tissue P systems generalize the membrane structure tree usual in original models of P systems to an arbitrary graph. Basic operations 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 andintractability. In this paper we show that computational power of these uniform families in polynomial time is limited by the class PSPACE. This class characterizes the power of many classical parallel computing models.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2013

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Membrane Computing

ISBN

978-3-642-36750-2

ISSN

0302-9743

e-ISSN

—

Number of pages

14

Pages from-to

390-403

Publisher name

Springer

Place of publication

Berlin

Event location

Budapest

Event date

Jan 1, 2012

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—