Solving HPP and SAT by P systems with active membranes and separation rules

Pan Linqiang; Alhazov Artiom

Conţinutul numărului revistei

Articolul precedent

Articolul urmator

SM ISO690:2012

PAN, Linqiang, ALHAZOV, Artiom. Solving HPP and SAT by P systems with active membranes and separation rules. In: Acta Informatica, 2006, vol. 43, pp. 131-145. ISSN 0001-5903. DOI: https://doi.org/10.1007/s00236-006-0018-8

EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core

Acta Informatica

Volumul 43 / 2006 / ISSN 0001-5903 /ISSNe 1432-0525

Solving HPP and SAT by P systems with active membranes and separation rules

DOI:https://doi.org/10.1007/s00236-006-0018-8

Pag. 131-145

Pan Linqiang¹², Alhazov Artiom³

¹ Huazhong University of Science and Technology,
² Universitat Rovira i Virgili - La universitat pública de Tarragona,
³ Institute of Mathematics and Computer Science ASM

Disponibil în IBN: 27 februarie 2024

Descarcă PDF

Rezumat

The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space - membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.

Cuvinte-cheie
Distributed parallel computing, Hamiltonian path problems, Hard problems, Membrane separation, Membrane system, P systems with active membranes, Polynomial-time, Satisfiability problems

Dublin Core Export

<?xml version='1.0' encoding='utf-8'?>
<oai_dc:dc xmlns:dc='http://purl.org/dc/elements/1.1/' xmlns:oai_dc='http://www.openarchives.org/OAI/2.0/oai_dc/' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xsi:schemaLocation='http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd'>
<dc:creator>Pan, L.</dc:creator>
<dc:creator>Alhazov, A.E.</dc:creator>
<dc:date>2006-08-01</dc:date>
<dc:description xml:lang='en'><p>The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space - membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.</p></dc:description>
<dc:identifier>10.1007/s00236-006-0018-8</dc:identifier>
<dc:source>Acta Informatica  () 131-145</dc:source>
<dc:subject>Distributed parallel computing</dc:subject>
<dc:subject>Hamiltonian path problems</dc:subject>
<dc:subject>Hard problems</dc:subject>
<dc:subject>Membrane separation</dc:subject>
<dc:subject>Membrane system</dc:subject>
<dc:subject>P systems with active membranes</dc:subject>
<dc:subject>Polynomial-time</dc:subject>
<dc:subject>Satisfiability problems</dc:subject>
<dc:title>Solving HPP and SAT by P systems with active membranes and separation rules</dc:title>
<dc:type>info:eu-repo/semantics/article</dc:type>
</oai_dc:dc>