On the computational completeness of several descriptional complexity restrictions of semi-conditional grammars

A semi-conditional grammar, introduced by Gheorghe Păun, is a form of regulated rewriting system where each rule consists of a context-free core rule <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>A</mml:mi> <mml:mo stretchy="false">→</mml:mo> <mml:mi>w</mml:mi> </mml:math> along with two strings <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:msub> <mml:mi>w</mml:mi> <mml:mo>+</mml:mo> </mml:msub> </mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:msub> <mml:mi>w</mml:mi> <mml:mo>−</mml:mo> </mml:msub> </mml:math> . The rule is applicable if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:msub> <mml:mi>w</mml:mi> <mml:mo>+</mml:mo> </mml:msub> </mml:math> (the positive condition) occurs as a substring of the current sentential form, but <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:msub> <mml:mi>w</mml:mi> <mml:mo>−</mml:mo> </mml:msub> </mml:math> (the negative condition) does not. The maximum lengths i , j of the positive or negative conditional strings, respectively, give a natural measure of descriptional complexity, known as the degree of such grammars. Employing several normal form results on phrase-structure grammars as derived in particular by Viliam Geffert, we improve on previously obtained results by reducing the number of nonterminals of semi-conditional grammars of a given degree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> while maintaining computational completeness of the said mechanisms.