A limitation of cell division in tissue P systems by PSPACE

Kód výsledku v IS VaVaI

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A limitation of cell division in tissue P systems by PSPACE

Popis výsledku v původním jazyce

P systems are abstract distributed computing models inspired by the information flows in living cells and their networks, with applications, e.g., in systems biology and optimization. A tissue P system is a variant based on the interchange of objects between cells due to an underlying communication graph. The model is further enriched with the operation of cell division. This operation allows to produce an exponential number of cells in polynomial time. The paper studies the computational power of polynomially uniform families of these systems. Previous studies demonstrated that they can cover problems ranging between P and NP ? co-NP due to the length of communication rules, thus characterizing a borderline between tractability and intractability. Weshow that, in spite of the exponential space the model can use, the problems solvable by these families in polynomial time lie within the class PSPACE.

Název v anglickém jazyce

A limitation of cell division in tissue P systems by PSPACE

Popis výsledku anglicky

P systems are abstract distributed computing models inspired by the information flows in living cells and their networks, with applications, e.g., in systems biology and optimization. A tissue P system is a variant based on the interchange of objects between cells due to an underlying communication graph. The model is further enriched with the operation of cell division. This operation allows to produce an exponential number of cells in polynomial time. The paper studies the computational power of polynomially uniform families of these systems. Previous studies demonstrated that they can cover problems ranging between P and NP ? co-NP due to the length of communication rules, thus characterizing a borderline between tractability and intractability. Weshow that, in spite of the exponential space the model can use, the problems solvable by these families in polynomial time lie within the class PSPACE.

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í

2015

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

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

81

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

473-484

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—