Computational completeness of minimal communication with small number of cells

Abstract Generalized communicating P systems (GCPSs for short) are a common generalization of tissue-like P systems (networks of cells) where each interaction rule can move only two objects through the cells. Depending on the source and target cells, nine types of such rules are distinguished. Previous works have shown that several GCPSs families where the GCPSs use only one type of rules and have only three cells are computationally complete devices. In this paper, we show that GCPSs with only parallel-shift rules and only four cells, and GCPSs with only presence-move rules and only three cells are computationally complete as well. With these new results, we contribute to the research goal of providing a sharp lower bound on the number of cells needed to achieve computational completeness for all families of GCPSs where GCPSs use only one type of interaction rules.