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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Matrix Forbidding Grammars

  • Henning Fernau,
  • Lakshmanan Kuppusamy,
  • Indhumathi Raman,
  • György Vaszil

摘要

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.