Inclusion algorithms for one-unambiguous regular expressions and their applications

摘要

One-unambiguous regular expressions are used in DTD and XML Schema. It is known that inclusion for one-unambiguous regular expressions is in PTIME. However, there has been few studies on algorithms for the inclusion. In this paper we present algorithms for checking inclusion of one-unambiguous regular expressions. A classical way is based on automata, following which one algorithm is provided and improvements are given. The other algorithm is based on derivatives, utilizing a property presented here that the number of derivatives of a one-unambiguous regular expression is finite. We have applied the algorithms to XML typechecking. The results of experiments with the algorithms are also included. First we give comparisons of the efficiency of our algorithms by experiments. Since after our work Hovland has given another algorithm, we also included his algorithm in the experiments. The results show that both of our algorithms are more efficient than Hovland's algorithm for one-unambiguous regular expressions, and under the inclusion mode (see Section 6) the derivative-based algorithm is more efficient than the automata-based one for small expressions, while for large expressions the latter is more efficient. Then we have conducted preliminary experiments by implementing typechecking of XML using the algorithms. The results show that typechecking using our algorithms is more efficient than typechecking using XDuce. Comparisons of the algorithms with CDuce are also given.