1. When catalytic P systems with one catalyst can be computationally complete
- Author
-
Rudolf Freund, Artiom Alhazov, Sergiu Ivanov, Vladimir Andrunachievici Institute of Mathematics and Computer Science, Faculty of Informatics, Vienna University of Technology (TU Wien), Informatique, BioInformatique, Systèmes Complexes (IBISC), and Université d'Évry-Val-d'Essonne (UEVE)-Université Paris-Saclay
- 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 - 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.
- Published
- 2021