基于边的图文法产生式选择无关条件的判断

摘要：

为了降低归约算法的时间复杂度,在基于边的上下文相关图文法(EGG)形式化的基础上,通过对产生式形式的适当约束,提出了EGG的产生式选择无关条件的判断方法.通过此方法可有效判断EGG产生式的选择无关性.对于选择无关的产生式,由于归约过程中产生式的使用顺序不会影响归约的结果,从而避免了回溯,能够有效地降低归约算法的时间复杂度.

关键词：选择无关、归约算法、时间复杂度、基于边的上下文相关图文法

所属期刊栏目：34

分类号：TP391.4(计算技术、计算机技术)

资助基金：湖北省教育厅科学研究计划项目Q20142607

在线出版日期：2015-01-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：3180-3183