Membrane Computing and Complexity Theory: A Characterization of PSPACE
Result description
A P system is a natural computing model inspired by information processing in cells and cellular membranes. We show that confluent P systems with active membranes solve in polynomial exactly the class of problems PSPACE. Consequently, these P systems prove to be equivalent (up to polynomial time reduction) to the alternating Turing machine or the PRAM computer.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
čeština
Original language name
Membránové výpočty a teorie složitosti: charakterizace třídy PSPACE
Original language description
P systém je abstraktní biovýpočetní model indpirovaný informačními procesy v buňkách a buněčných membránách. Ukážeme, že konfluentní P systémy s aktivními membránami řeší v polynomiálním čase přesně třídu problémů PSPACE. V důsledku toho jsou tyto P systémy ekvivalentní (vzhledem k polynomiální redukci) alternujícím Turingovým strojům anebo modelu PRAM.
Czech name
Membránové výpočty a teorie složitosti: charakterizace třídy PSPACE
Czech description
P systém je abstraktní biovýpočetní model indpirovaný informačními procesy v buňkách a buněčných membránách. Ukážeme, že konfluentní P systémy s aktivními membránami řeší v polynomiálním čase přesně třídu problémů PSPACE. V důsledku toho jsou tyto P systémy ekvivalentní (vzhledem k polynomiální redukci) alternujícím Turingovým strojům anebo modelu PRAM.
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
GA201/06/0567: Bioinformatics and biocomputing: connections, models and applications
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN
0022-0000
e-ISSN
—
Volume of the periodical
73
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
15
Pages from-to
137-151
UT code for WoS article
—
EID of the result in the Scopus database
—
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
IN - Informatics
Year of implementation
2007