Inclusion algorithms for one-unambiguous regular expressions and their applications
Inclusion algorithms for one-unambiguous regular expressions and their applications
复制标题
一明确正则表达式的包含算法及其应用
DOI：
10.1016/j.scico.2020.102436
复制
发表时间：
2020-07
影响因子：
1.3
通讯作者：
Xu Zhiwu
中科院分区：
文献类型：
--
作者：
Chen Haiming;Xu Zhiwu
在DTD和XML Schema中使用一元明确的正则表达式。众所周知，包含一个明确的正则表达式是在PTIME。然而，有几个算法的研究纳入。在本文中，我们提出了算法检查包含一个明确的正则表达式。一种经典的方法是基于自动机的，然后给出了一种算法，并给出了改进。另一种算法是基于导数，利用这里提出的一个属性，即一个明确的正则表达式的导数的数量是有限的。我们已经应用到XML类型检查的算法。最后给出了算法的实验结果。首先通过实验比较了我们算法的效率。由于在我们的工作之后Hovland给出了另一个算法，我们也将他的算法包括在实验中。结果表明，对于一元正则表达式，我们的算法都比Hovland的算法更有效;在包含模式下（见第6节），对于小表达式，基于导数的算法比基于自动机的算法更有效，而对于大表达式，基于自动机的算法更有效。然后，我们进行了初步的实验，实现了XML的类型检查使用的算法。结果表明，使用我们的算法的类型检查比使用XDuce的类型检查更有效。并与CDuce算法进行了比较。
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.
登录
查看更多内容
DOI：
10.1007/3-540-45446-2_12
发表时间：
2001-10
期刊：
--
影响因子：
--
作者：
D. Giammarresi;R. Montalbano;D. Wood
通讯作者：
D. Giammarresi;R. Montalbano;D. Wood
DOI：
10.1145/2535838.2535840
发表时间：
2014-01
期刊：
Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Giuseppe Castagna;K. Nguyen;Zhiwu Xu;Hyeonseung Im;Sergueï Lenglet;L. Padovani
通讯作者：
Giuseppe Castagna;K. Nguyen;Zhiwu Xu;Hyeonseung Im;Sergueï Lenglet;L. Padovani
DOI：
10.21236/ada240494
发表时间：
1991-06
期刊：
--
影响因子：
--
作者：
Alain J. Mayer;L. Stockmeyer
通讯作者：
Alain J. Mayer;L. Stockmeyer
DOI：
10.1007/3-540-60249-6_44
发表时间：
1995-08
期刊：
--
影响因子：
--
作者：
Valentin M. Antimirov
通讯作者：
Valentin M. Antimirov
影响因子：
--
作者：
Giuseppe Castagna;K. Nguyen;Zhiwu Xu;P. Abate
通讯作者：
Giuseppe Castagna;K. Nguyen;Zhiwu Xu;P. Abate