Efficiency of Tissue P Systems with Cell Separation

Abstract

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.