Counting Simple Rules in Semi-conditional Grammars is not Simple

A semi-conditional grammar is a form of regulated rewriting system. Each rule consists of a context-free core rule \(A\rightarrow w\) and (possibly) two strings \(w_+,w_-\) ; the rule is applicable if  \(w_+\) (the permitting string) occurs as a substring of the current sentential form, but  \(w_-\) (the forbidden string) does not. The maximum lengths i, j of the permitting or forbidden strings, respectively, give a natural measure of descriptional complexity, known as the degree of such grammars. Such a grammar is called simple if for each rule, either the permitting or the forbidden string is missing. As the simplicity requirement turns out to be a severe restriction and causes other descriptional complexity parameters to grow, we refine the study by introducing, as an additional parameter, the number of non-simple rules. Employing several normal form results on phrase-structure grammars as derived by Geffert (1991) and Masopust and Meduna (2007), we prove several new computational completeness results that interpolate between what was known so far on general and simple semi-conditional grammars.