On the computational completeness of graph-controlled insertion-deletion systems with binary sizes

In this paper, we discuss the computational completeness of the families of GCID systems of size (k;1,i′,i″;1,j′,j″) with k∈{3,5} and for (nearly) all values of i′,i″j′,j″∈{0,1}. All proofs are based on the simulation of type-0 grammars given in Special Geffert Normal Form (SGNF). The novelty in our proof presentation is that the context-free and the non-context-free rules of the given SGNF grammar are simulated by GCID systems of different sizes and finally we combine them by stitching and overlaying to characterize the recursive enumerable languages. This proof presentation greatly simplifies and unifies the proof of such characterization results. We also connect some of the obtained GCID simulations to the domain of insertion-deletion P systems.