XML由于简单灵活和良好的可扩展性,在网络服务、关系数据库以及形式化研究等领域得到了应用。随着XML处理技术的不断发展,近期的研究表明静态类型化处理方式在XML处理时具有重要的优势。在静态类型化系统中,XML的模式语言被当作程序的基本类型,在编译时静态地检查子类型关系,以确保程序运行时的类型安全。在很多情况下,XML类型检查与XML模式语言中的正则表达式的包含判定有很大的联系。　　 在针对产生式不相交的正规树文法的XML类型检查中,需要对正规树文法的产生式进行相交判定。基于正规树文法的产生式的构成特点,本文提出了基于自动机的产生式相交判定算法。根据产生式的内容模型即正则表达式,构建相应自动机,然后判定两个自动机的交是否为空,算法的时间复杂度为O(‖E1‖·‖E2‖·｜∑E1∪∑E2｜)。实验数据表明,该算法是可行的,可以应用到针对产生式不相交的正规树文法的XML类型检查中。　　 本文还研究了正则表达式的包含判定算法。正则表达式的包含判定是XML类型检查中的一个重要问题,目前主要有基于自动机(DFA)、基于正则表达式推导、基于正则表达式Header-form推导等三种算法。其中,前两种算法主要针对的是one-unambiguous正则表达式,第三种算法则可以针对普通的正则表达式,只是在某些情况下,该算法无法对某些非one—ambiguous正则表达式进行包含判定,这时该算法会报告此问题。本文实现了以上三种算法,并通过实验对比分析了三种算法的实际运行效率,在此基础上,本文针对正则表达式的包含判定问题,提出了一个综合的包含判定算法。该综合算法可以针对普通的正则表达式进行包含判定,并且针对输入的正则表达式的部分子集,采用了实际运行效率更高的包含判定算法(上述三种算法之一),因而在一定程度上提高了算法的整体运行效率。本文同时实现了该综合算法,且通过的相应的实验证明了该综合算法的可行性。