Computational Completeness of Simple Semi-conditional Insertion-Deletion Systems

摘要

Insertion-deletion (or ins-del for short) systems are well studied in formal language theory, especially regarding their computational completeness. The need for many variants on ins-del systems was raised by the computational completeness result of ins-del system with (optimal) size (1,1,1;1,1,1). Several regulations like graph-control, matrix and semi-conditional have been imposed on ins-del systems. Typically, computational completeness are obtained as trade-off results, reducing the size, say, to (1,1,0,1,1,0) at the expense of increasing other measures of descriptional complexity. In this paper, we study simple semi-conditional ins-del systems, where an ins-del rule can be applied only in the presence or absence of substrings of the derivation string. We show that simple semi-conditional ins-del system, with maximum permitting string length 2 and maximum forbidden string length 1 and sizes (2,0,0;2,0,0), (1,1,0;2,0,0), or (1,1,0;1,1,1), are computationally complete. We also describe RE by a simple semi-conditional ins-del system of size (1,1,0;1,1,0) and with maximum permitting and forbidden string lengths 3 and 1, respectively. The obtained results complement the existing results available in the literature.