Affiliations: [a] Abteilung Informatikwissenschaften, Fachbereich 4, Universität Trier, D-54286 Trier, Germany | [b] School of Computer Science & Engineering, Vellore Institute of Technology, Vellore – 632 014, India | [c] Department of Computer Science, University of Ilorin, P.M.B.1515, Ilorin, Nigeria
Abstract: 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 A→w along with two strings w+, w−. The rule is applicable if w+ (the positive condition) occurs as a substring of the current sentential form, but w− (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 (i,j) while maintaining computational completeness of the said mechanisms.
