On the power of computing with proteins on membranes.
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F10%3A%230003016" target="_blank" >RIV/47813059:19240/10:#0003016 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
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ů
Údaje specifické pro druh výsledku
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
—