Research Group on Natural Computing

The most investigated variants of P systems in the last years are cell-like
models, especially in terms of efficiency. Recently, different new models of tissue-like
(symport/antiport) P systems have received important attention. This paper presents a
new class of tissue P systems with cell separation, where cell separation can generate new
workspace. Its efficiency is investigated, specifically, (a) only tractable problem can be
efficiently solved by using cell separation and communication rules with length at most
1, and (b) an efficient (uniform) solution to SAT problem by using cell separation and
communication rules with length at most 6 is presented. Further research topics and open
problems are discussed, too.