Limits of the power of tissue P systems with cell division

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Limits of the power of tissue P systems with cell division

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Limits of the power of tissue P systems with cell division

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: Centrum excelence IT4Innovations</a><br>

Návaznosti

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

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název statě ve sborníku

Membrane Computing

ISBN

978-3-642-36750-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

390-403

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Budapest

Datum konání akce

1. 1. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—