Minimal Parallelism and Number of Membrane Polarizations
It is known that the satisfiability problem ({\tt 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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2010-11-01
|
| Series: | Computer Science Journal of Moldova |
| Online Access: | http://www.math.md/files/csjm/v18-n2/v18-n2-(pp149-170).pdf |
| _version_ | 1798003495252525056 |
|---|---|
| author | Artiom Alhazov |
| author_facet | Artiom Alhazov |
| author_sort | Artiom Alhazov |
| collection | DOAJ |
| description | It is known that the satisfiability problem ({\tt 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 sufficient for an efficient 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. |
| first_indexed | 2024-04-11T12:08:29Z |
| format | Article |
| id | doaj.art-6d2ae6ce532943cf8a5e2f958910af2c |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-11T12:08:29Z |
| publishDate | 2010-11-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-6d2ae6ce532943cf8a5e2f958910af2c2022-12-22T04:24:40ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422010-11-01182(53)149170Minimal Parallelism and Number of Membrane PolarizationsArtiom Alhazov0 Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, 5 Academiei str., Chisinau, MD-2028, Moldova; FCS, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8527 JapanIt is known that the satisfiability problem ({\tt 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 sufficient for an efficient 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.http://www.math.md/files/csjm/v18-n2/v18-n2-(pp149-170).pdf |
| spellingShingle | Artiom Alhazov Minimal Parallelism and Number of Membrane Polarizations Computer Science Journal of Moldova |
| title | Minimal Parallelism and Number of Membrane Polarizations |
| title_full | Minimal Parallelism and Number of Membrane Polarizations |
| title_fullStr | Minimal Parallelism and Number of Membrane Polarizations |
| title_full_unstemmed | Minimal Parallelism and Number of Membrane Polarizations |
| title_short | Minimal Parallelism and Number of Membrane Polarizations |
| title_sort | minimal parallelism and number of membrane polarizations |
| url | http://www.math.md/files/csjm/v18-n2/v18-n2-(pp149-170).pdf |
| work_keys_str_mv | AT artiomalhazov minimalparallelismandnumberofmembranepolarizations |