Back to Search
Start Over
When catalytic P systems with one catalyst can be computationally complete
- Source :
- Journal of Membrane Computing, Journal of Membrane Computing, 2021, 3, pp.170--181. ⟨10.1007/s41965-021-00079-x⟩
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst in the whole system: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining computational completeness even with only one catalyst. In this paper, we show that one catalyst is sufficient for obtaining computational completeness if either catalytic rules have weak priority over non-catalytic rules or else instead of the standard maximally parallel derivation mode, we use the derivation mode maxobjects, i.e., we only take those multisets of rules which affect the maximal number of objects in the underlying configuration.
- Subjects :
- [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Catalytic rules
Computational complexity theory
Computer science
Applied Mathematics
P systems
Priority of catalytic rules
Derivation mode maxobjects
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Catalysis
Whole systems
Recursively enumerable language
Computational Theory and Mathematics
010201 computation theory & mathematics
Theory of computation
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Completeness (statistics)
Algorithm
Subjects
Details
- ISSN :
- 25238914 and 25238906
- Volume :
- 3
- Database :
- OpenAIRE
- Journal :
- Journal of Membrane Computing
- Accession number :
- edsair.doi.dedup.....0683b88f02af28bb5ea66d4541751b99