Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
657 2 |
Ultima descărcare din IBN: 2017-04-28 11:27 |
Căutarea după subiecte similare conform CZU |
519.652 (4) |
Matematică computațională. Analiză numerică. Programarea calculatoarelor (123) |
SM ISO690:2012 ALHAZOV, Artiom. Minimal Parallelism and Number of Membrane
Polarizations. In: Computer Science Journal of Moldova, 2010, nr. 2(53), pp. 149-170. ISSN 1561-4042. |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Computer Science Journal of Moldova | ||||||
Numărul 2(53) / 2010 / ISSN 1561-4042 /ISSNe 2587-4330 | ||||||
|
||||||
CZU: 519.652 | ||||||
Pag. 149-170 | ||||||
|
||||||
Descarcă PDF | ||||||
Rezumat | ||||||
It is known that the satisfiability problem (SAT) can be efficiently solved by a uniform family of P systems with active membranes with two polarizations working in a maximally parallel way. We study P systems with active membranes without non-elementary membrane division, working in minimally parallel way. The main question we address is what number of polarizations is su±cient for an e±cient computation depending on the types of rules used. In particular, we show that it is enough to have four polarizations, sequential evolution rules changing polarizations, polarizationless non-elementary membrane division rules and polarizationless rules of sending an object out. The same problem is solved with the standard evolution rules, rules of sending an object out and polarizationless non-elementary membrane division rules, with six polarizations. It is an open question whether these numbers are optimal. |
||||||
|