Trading polarizations for labels in P systems with active membranes
Închide
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

Trading polarizations for labels in P systems with active membranes

DOI:https://doi.org/10.1007/s00236-004-0153-z

Pag. 111-144

Alhazov Artiom12, Pan Linqiang13, Păun Gheorghe45
 
1 Universitat Rovira i Virgili - La universitat pública de Tarragona,
2 Institute of Mathematics and Computer Science ASM,
3 "Simion Stoilov" Institute of Mathematics of Romanian Academy,
4 "Simion Stoilov" Institute of Mathematics of Romanian Academy,
5 University of Sevilla
 
 
Disponibil în IBN: 27 februarie 2024


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