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

• 作者: 刘嘉 廖湖声
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: XML类型检查 正规式 相交判定 推导规则
• 年，卷（期）: 2015,（1）
• 所属期刊栏目: 数据库技术
• 页码范围: 43-50
• 页数: 8页
• 分类号: TP311
• 字数: 7833字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1407042

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘嘉	北京工业大学计算机学院	62	729	13.0	25.0
2	廖湖声	北京工业大学计算机学院	79	473	11.0	18.0