P systems with active membranes characterize PSPACE

Result code in IS VaVaI

RIV/47813059:19240/01:#0001874 - isvavai.cz

Alternative codes found

RIV/47813059:19240/06:#0003239

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

P systems with active membranes characterize PSPACE

Original language description

A P system is a natural computing model inspired by information processes in cells and a control role of cellular membranes. We show that uniform families of P systems with active membranes are able to solve, in polynomial time, exactly the class of decisional problems PSPACE. Similar results were achieved also with other models of bio-inspired computers, such as DNA computing. Together they suggest that PSPACE naturally characterizes the computational potential of biological information processing.

Czech name

P systémy s aktivními membránami charakterizují PSPACE

Czech description

P systém je výpočetní model inspirovaný informačními procesy v buňkách a regulační úlohou buněčných membrán. Ukážeme, že uniformní sekvence P systémů s aktivními membránami dokáží řešit v polynomiálním čase třídu problémů rovnou PSPACE.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2006

Confidentiality

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

Article name in the collection

DNA Computing

ISBN

978-3-540-49024-1

ISSN

0302-9743

e-ISSN

—

Number of pages

14

Pages from-to

—

Publisher name

—

Place of publication

Berlin

Event location

Seoul

Event date

Jan 1, 2006

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—