Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
89 0 |
SM ISO690:2012 ALHAZOV, Artiom, PAN, Linqiang, PĂUN, Gheorghe. Trading polarizations for labels in P systems with active membranes. In: Acta Informatica, 2004, vol. 41, pp. 111-144. ISSN 0001-5903. DOI: https://doi.org/10.1007/s00236-004-0153-z |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Acta Informatica | |
Volumul 41 / 2004 / ISSN 0001-5903 /ISSNe 1432-0525 | |
|
|
DOI:https://doi.org/10.1007/s00236-004-0153-z | |
Pag. 111-144 | |
Descarcă PDF | |
Rezumat | |
This paper addresses the problem of removing the polarization of membranes from P systems with active membranes - and this is achieved by allowing the change of membrane labels by means of communication rules or by membrane dividing rules. As consequences of these results, we obtain the universality of P systems with active membranes which are allowed to change the labels of membranes, but do not use polarizations. Universality results are easily obtained also by direct proofs. By direct constructions, we also prove that SAT can be solved in linear time by systems without polarizations and with label changing possibilities. If non-elementary membranes can be divided, then SAT can be solved in linear time without using polarizations and label changing. Several open problems are also formulated. |
|
Cuvinte-cheie computer architecture, computer simulation, membranes, Parallel processing systems, polarization, polynomials, problem solving |
|
|