The Power of Symport-3 with Few Extra Symbols
Închide
Articolul precedent
Articolul urmator
272 0
SM ISO690:2012
ALHAZOV, Artiom, ROGOZHIN, Yurii. The Power of Symport-3 with Few Extra Symbols. In: Brainstorming Week On Membrane Computing, 30 ianuarie - 3 februarie 2012, Sevilla. Sevilla, Spania: Fénix Editora, 2012, Ediția a 10-a, pp. 61-67.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Brainstorming Week On Membrane Computing
Ediția a 10-a, 2012
Masa rotundă "Tenth Brainstorming Week on Membrane Computing"
Sevilla, Spania, 30 ianuarie - 3 februarie 2012

The Power of Symport-3 with Few Extra Symbols


Pag. 61-67

Alhazov Artiom12, Rogozhin Yurii2
 
1 University of Milano-Bicocca,
2 Institute of Mathematics and Computer Science ASM
 
 
Disponibil în IBN: 15 mai 2021


Rezumat

Membrane systems (with symbol objects) are formal models of distributed parallel multiset processing. Symport rules move multiple objects to a neighboring region. It is known that P systems with symport rules of weight at most 3 and a single membrane are computationally complete with 7 superfluous symbols. It is also known that without any superfluous symbols such systems only generate finite sets. We improve the lower bounds on the generative power of P systems with few superfluous objects as follows. 0: empty set and all singletons; k: all sets with at most k elements and all sets of numbers k+regular with up to k states, 1  k  5; 6: all regular sets of non-negative integers. All results except the last one are also valid for different modes, e.g., sequential one, also for higher values of k.