Tissue P systems with cell separation: Upper bound by PSPACE

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007/978-3-642-33860-1_17" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-642-33860-1_17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-33860-1_17" target="_blank" >10.1007/978-3-642-33860-1_17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Tissue P systems with cell separation: Upper bound by PSPACE

Popis výsledku v původním jazyce

Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. This organization is formally described by an interaction graph with membranes at its vertices. Membranes communicate by exchanging objects from a finite set. This basic model was enhanced with the operation of cell separation, resulting in tissue P systems with cell separation. Uniform families of tissue P systems were recently studied. Their computational power was shown to range between P and NP U co - NP, characterizing borderlines between tractability and intractability by length of rules and some other features. Here we show that the computational power of these uniform families in polynomial time is limited from above by the class PSPACE. In this way we relate the information-processing potential of bio-inspired tissue-like systems to classical parallel computing models as PRAM or alternating Turing machine.

Název v anglickém jazyce

Tissue P systems with cell separation: Upper bound by PSPACE

Popis výsledku anglicky

Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. This organization is formally described by an interaction graph with membranes at its vertices. Membranes communicate by exchanging objects from a finite set. This basic model was enhanced with the operation of cell separation, resulting in tissue P systems with cell separation. Uniform families of tissue P systems were recently studied. Their computational power was shown to range between P and NP U co - NP, characterizing borderlines between tractability and intractability by length of rules and some other features. Here we show that the computational power of these uniform families in polynomial time is limited from above by the class PSPACE. In this way we relate the information-processing potential of bio-inspired tissue-like systems to classical parallel computing models as PRAM or alternating Turing machine.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

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í

2012

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 periodika

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Svazek periodika

7505

Číslo periodika v rámci svazku

zima

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

15

Strana od-do

201-215

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—