论文部分内容阅读
摘要：在针对产生式不相交的正规树文法的XML类型检查中，需要对正规树文法的产生式进行相交判定。基于正规树文法的产生式的构成特点，提出了基于自动机的相交判定算法。根据产生式的内容模型即正则表达式，构建相应自动机，判定两个自动机的交是否为空，该算法的时间复杂度为0（丨丨E1丨丨·丨E2丨丨·丨∑E1∑E2丨）。实验结果表明，该算法运行正确且高效，可以应用到针对产生式不相交的正规树文法的XML类型检查中。