Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. In traditional regulated rewriting, the most interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on forbidding sets, i.e., a matrix is applicable to a sentential form w only if none of the words in its forbidding set occurs as a subword in w. This gives rise to further natural descriptional complexity measures: How long could words in forbidding sets be? How many words could be in any forbidding set? How many matrices contain non-empty forbidding contexts? As context-free grammars with forbidding sets are known as generalized forbidding grammars, we call this variant of matrix grammars also generalized forbidding. In this paper, we attempt to answer the four questions above while studying the computational completeness of generalized forbidding matrix grammars. In the course of our studies, we also define several new normal forms for type-0 grammars that might be of independent interest.

A simple semi-conditional (SSC) grammar is a form of regulated rewriting system where the derivations are controlled either by a permitting string alone or by a forbidden string alone and this condition is specified in the rule. The maximum length i (j, resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional rules are also counted into the descriptional complexity measures of these grammars. We improve on some previously obtained results on the computational completeness of SSC grammars by minimizing the number of nonterminals and / or the number of conditional rules for a given degree (i, j). More specifically we prove, using a refined analysis of a normal form for type-0 grammars due to Geffert, that every recursively enumerable language is generated by an SSC grammar of (i) degree (2, 1) with eight conditional rules and nine nonterminals, (ii) degree (3, 1) with seven conditional rules and seven nonterminals (iii) degree (4, 1) with six conditional rules and seven nonterminals and (iv) degree (4, 1) with eight conditional rules and six nonterminals.

Abstract A matrix insertion-deletion system (or matrix ins-del system) is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model very simplistic fragments of sequential programs based on insertion and deletion as elementary operations as can be found in biocomputing. We are investigating such systems with limited resources as formalized in descriptional complexity. A traditional descriptional complexity measure of such a matrix ins-del system is its size $$s=(k;n,i',i'';m,j',j'')$$ s = ( k ; n , i ′ , i ′ ′ ; m , j ′ , j ′ ′ ) , where the parameters from left to right represent the maximal matrix length, maximal insertion string length, maximal length of left contexts in insertion rules, maximal length of right contexts in insertion rules; the last three are deletion counterparts of the previous three parameters. We call the sum $$n+i'+i''+m+j'+j''$$ n + i ′ + i ′ ′ + m + j ′ + j ′ ′ the sum-norm of s. We show that matrix ins-del systems of sum-norm 4 and sizes (3; 1, 0, 0; 1, 2, 0), (3; 1, 0, 0; 1, 0, 2), (2; 1, 2, 0; 1, 0, 0), (2; 1, 0, 2; 1, 0, 0), and (2; 1, 1, 1; 1, 0, 0) describe the recursively enumerable languages. Moreover, matrix ins-del systems of sizes (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0) can describe at least the regular closure of the linear languages. In fact, we show that if a matrix ins-del system of size s can describe the class of linear languages $$\mathrm {LIN}$$ LIN , then without any additional resources, matrix ins-del systems of size s also describe the regular closure of $$\mathrm {LIN}$$ LIN . Finally, we prove that matrix ins-del systems of sizes (2; 1, 1, 0; 1, 1, 0) and (2; 1, 0, 1; 1, 0, 1) can describe at least the regular languages.