Tissue P systems with cell separation: Upper bound by PSPACE
Result description
Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. This organization is formally described by an interaction graph with membranes at its vertices. Membranes communicate by exchanging objects from a finite set. This basic model was enhanced with the operation of cell separation, resulting in tissue P systems with cell separation. Uniform families of tissue P systems were recently studied. Their computational power was shown to range between P and NP U co - NP, characterizing borderlines between tractability and intractability by length of rules and some other features. Here we show that the computational power of these uniform families in polynomial time is limited from above by the class PSPACE. In this way we relate the information-processing potential of bio-inspired tissue-like systems to classical parallel computing models as PRAM or alternating Turing machine.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
http://link.springer.com/chapter/10.1007/978-3-642-33860-1_17
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
Tissue P systems with cell separation: Upper bound by PSPACE
Original language description
Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. This organization is formally described by an interaction graph with membranes at its vertices. Membranes communicate by exchanging objects from a finite set. This basic model was enhanced with the operation of cell separation, resulting in tissue P systems with cell separation. Uniform families of tissue P systems were recently studied. Their computational power was shown to range between P and NP U co - NP, characterizing borderlines between tractability and intractability by length of rules and some other features. Here we show that the computational power of these uniform families in polynomial time is limited from above by the class PSPACE. In this way we relate the information-processing potential of bio-inspired tissue-like systems to classical parallel computing models as PRAM or alternating Turing machine.
Czech name
—
Czech description
—
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2012
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
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Volume of the periodical
7505
Issue of the periodical within the volume
zima
Country of publishing house
DE - GERMANY
Number of pages
15
Pages from-to
201-215
UT code for WoS article
—
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
IN - Informatics
Year of implementation
2012