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

作     者：刘嘉 廖湖声 LIU Jia;LIAO Husheng

作者机构：北京工业大学计算机学院北京100124 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2015年第9卷第1期

页      面：43-50页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：北京市自然科学基金No.4082003 

主　　题：XML类型检查 正规式 相交判定 推导规则 

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