An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F15%3A%230005525" target="_blank" >RIV/47813059:19240/15:#0005525 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

Popis výsledku v původním jazyce

A membrane system P system is a distributed computing model inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can besolved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderlin

Název v anglickém jazyce

An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

Popis výsledku anglicky

A membrane system P system is a distributed computing model inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can besolved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderlin

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: Centrum excelence IT4Innovations</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

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ů

Název periodika

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

—

Svazek periodika

138

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

45-60

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—