首页> 外文期刊>International Journal of Pattern Recognition and Artificial Intelligence >A HIERARCHY RESULT FOR RANDOM FORBIDDING CONTEXT PICTURE GRAMMARS
【24h】

A HIERARCHY RESULT FOR RANDOM FORBIDDING CONTEXT PICTURE GRAMMARS

机译:随机禁止上下文图片语法的层次结构结果

获取原文
获取原文并翻译 | 示例
       

摘要

We use random context picture grammars to generate pictures through successive refinement. The productions of such a grammar are context-free, but their application is regulate - "permitted" or "forbidden"-by context randomly distributed in the developing picture. Grammars using this relatively weak context often succeed where context-free grammars fail, e.g. in generating the Sierpinski carpets. On the other hand it proved possible to develop iteration theorems for three subclasses of these grammars, namely a pumping-shrinking, a pumping and a shrinking lemma for context-free, random permitting and random forbidding context picture grammars, respectively. Finding necessary conditions is problematic in the case of most models of context-free grammars necessary conditions is problematic in the case of most models of context-free grammars with context-sensing ability, since they consider a variable and its context as a finite connected array. We have already shown that context-free picture grammars are strictly weaker than both random permitting and random forbidding context picture grammars, also that random permitting context is strictly weaker than random context. We show that grammars which use forbidding context only are strictly weaker than random context picture grammars.
机译:我们使用随机上下文图片语法通过连续细化生成图片。这种语法的产生是无上下文关系的,但是它们的应用是受监管的-“允许的”或“禁止的”-由上下文随机分布在正在发展的画面中。使用这种相对较弱的上下文的语法通常会在无上下文语法失败的情况下成功,例如在生产Sierpinski地毯方面。另一方面,证明有可能针对这些语法的三个子类开发迭代定理,即分别针对无上下文,随机允许和随机禁止上下文图片语法的抽水收缩,抽水和收缩引理。在大多数上下文无关文法模型中,找到必要条件是有问题的,对于大多数具有上下文感知能力的上下文文法模型来说,必要条件是有问题的,因为它们将变量及其上下文视为有限连接数组。我们已经表明,无上下文的图片语法比随机允许和随机禁止的上下文图片语法都严格弱,而且随机允许的上下文比随机上下文严格更弱。我们证明,仅使用禁止上下文的语法比随机上下文图片语法严格弱。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号