Earticle

초록

영어

Decision problem of intersection checking for regular expressions plays an important role in the XML type checking. The typical technique is converted into the problem of automata intersection, which may generate a lot of redundant computing during the conversion. In the present paper, according to the features of XML schema languages, a new intersection checking algorithm based on inference system for regular expressions is proposed. This method is derived directly based on regular expression without the need for any conversion. For general regular expressions that is exponential time algorithm, but without constructing automata and for some special cases, especially for the one-unambiguous regular expressions used in XML type checking, is the polynomial time algorithm. Proofs of the correctness and completeness of the inference rules are given. Experiment results show that our approach are more effective than automatic approach in practical.

목차

Abstract
 1. Introduction
 2. Definitions
 3. Rules for Intersection
 4. Properties of the Rules
 5. Algorithm and Examples
 6. Experiments
 7. Relation Works
 8. Conclusion
 Acknowledgements
 References

키워드

저자

• Jia Liu [ College of Computer Science, Beijing University of Technology, Beijing, China ]
• Husheng Liao [ College of Computer Science, Beijing University of Technology, Beijing, China ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Database Theory and Application

• 간기

  격월간

• pISSN

  2005-4270

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605