Indexed by:
Abstract:
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. © 2015 SERSC.
Keyword:
Reprint Author's Address:
Email:
Source :
International Journal of Database Theory and Application
ISSN: 2005-4270
Year: 2015
Issue: 4
Volume: 8
Page: 241-250
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 9
Affiliated Colleges: