基于规则推导的正规式相交判定算法

摘要：

正规式相交判定问题在扩展标记语言（extensible markup language，XML）类型检查中起着十分重要的作用。传统方法是将其转化为自动机的相交问题，在转化过程中会产生大量计算。基于XML模式语言的特点，提出了一种基于规则推导的正规式相交判定算法。该算法直接根据输入的正规式进行推导而无需进行任何转化计算。对于一般的正规式，尽管其仍然是指数级算法，但无需进行复杂的构造自动机的计算；而对于一些特殊的正规式，特别是在XML类型检查中广泛使用的One-Unambiguous正规式，该算法的时间复杂度降为多项式级。最后证明了该算法所使用的推导规则的正确性和完备性。

关键词：XML类型检查、正规式、相交判定、推导规则

分类号：TP311(计算技术、计算机技术)

资助基金：The Natural Science Foundation of Beijing of China under Grant No.4082003

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

页数：共8页

页码：43-50