On the power of computing with proteins on membranes.

Kód výsledku v IS VaVaI

RIV/47813059:19240/10:#0003016 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On the power of computing with proteins on membranes.

Popis výsledku v původním jazyce

P systems with proteins on membranes are closely inspired by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterizethe class of problems solvable by these P systems in polynomial time and we show that it equals PSPACE. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer.The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins.

Název v anglickém jazyce

On the power of computing with proteins on membranes.

Popis výsledku anglicky

P systems with proteins on membranes are closely inspired by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterizethe class of problems solvable by these P systems in polynomial time and we show that it equals PSPACE. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer.The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2010

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

In G. Paun et al. (Eds.), Membrane Computing

ISBN

978-3-642-11466-3

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

—

Název nakladatele

Berlin: Springer-Verlag

Místo vydání

Berlín, Německo

Místo konání akce

Curtea de Arges, Romania

Datum konání akce

1. 1. 2009

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

WRD - Celosvětová akce

Kód UT WoS článku

—