Matrix Forbidding Grammars
摘要
Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. Semi-conditional grammars introduced the notion of permitting and forbidding contexts in context-free rules. In this paper, we introduce a new form of matrix grammars, called matrix forbidding grammars, where matrices of context-free rules are considered and each context-free rule is associated with a context so that a rule (in a matrix) can be applied only if this context is not a subword of the current sentential form. For matrix forbidding grammars, we study a range of descriptional complexity parameters, such as degree (length of forbidden contexts), number of nonterminals, number of conditional rules, number of matrices containing conditional rules, and matrix length, in order to explore the Pareto frontier (set of solutions that represents the best trade-off between all the parameters) of computational completeness.