Tissue P systems with cell separation: Upper bound by PSPACE

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Tissue P systems with cell separation: Upper bound by PSPACE

Original language description

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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

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

2012

Confidentiality

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

Name of the periodical

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Volume of the periodical

7505

Issue of the periodical within the volume

zima

Country of publishing house

DE - GERMANY

Number of pages

15

Pages from-to

201-215

UT code for WoS article

—

EID of the result in the Scopus database

—