科研之友
微信
新浪微博
Facebook
分享链接
摘要
在针对产生式不相交的正规树文法的XML类型检查中,需要对正规树文法的产生式进行相交判定。基于正规树文法的产生式的构成特点,提出了基于自动机的相交判定算法。根据产生式的内容模型即正则表达式,构建相应自动机,判定两个自动机的交是否为空,该算法的时间复杂度为O(‖E1‖.‖E2‖.|∑E1∪∑E2|)。实验结果表明,该算法运行正确且高效,可以应用到针对产生式不相交的正规树文法的XML类型检查中。
-
单位中国科学院研究生院; 中国科学院软件研究所; 计算机科学国家重点实验室
