A limitation of cell division in tissue P systems by PSPACE

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F15%3A%230005526" target="_blank" >RIV/47813059:19240/15:#0005526 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
A limitation of cell division in tissue P systems by PSPACE
Original language description
P systems are abstract distributed computing models inspired by the information flows in living cells and their networks, with applications, e.g., in systems biology and optimization. A tissue P system is a variant based on the interchange of objects between cells due to an underlying communication graph. The model is further enriched with the operation of cell division. This operation allows to produce an exponential number of cells in polynomial time. The paper studies the computational power of polynomially uniform families of these systems. Previous studies demonstrated that they can cover problems ranging between P and NP ? co-NP due to the length of communication rules, thus characterizing a borderline between tractability and intractability. Weshow that, in spite of the exponential space the model can use, the problems solvable by these families in polynomial time lie within the class PSPACE.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)