• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Liu, Jia (Liu, Jia.) | Liao, Husheng (Liao, Husheng.) (Scholars:廖湖声)

Indexed by:

EI

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:

Pattern matching Automata theory XML Polynomial approximation Computer programming languages Algorithms Inference engines

Author Community:

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

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

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

Online/Total:585/10704902
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.