Efficient Second-Order Matching
Efficient Second-Order Matching
复制标题
高效的二阶匹配
DOI：
10.1007/3-540-61464-8_62
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
H. Shi
中科院分区：
文献类型：
--
作者：
Régis Curien;Zhenyu Qian;H. Shi
Huet提出的标准二阶匹配算法可以扩展到柔性-刚性对的匹配。一方面，可能需要引入许多新鲜的自由变量;另一方面，尝试将灵活侧的标题自由变量与刚性侧的每个“顶层”相匹配，并将标题自由变量的每个参数与“顶层”覆盖的每个子项相匹配。提出了一种新的二阶匹配算法，该算法不引入新的自由变量，只考虑选定的“顶层”、标题自由变量的自变量以及相应“顶层”所覆盖的子项。第一个实现表明，新算法是更有效的时间和空间比标准的大量匹配问题。
The standard second-order matching algorithm by Huet may be expansive in matching a flexible-rigid pair. On one hand, many fresh free variables may need to be introduced; on the other hand, attempts are made to match the heading free variable on the flexible side with every “top layer” on the rigid side and every argument of the heading free variable with every subterm covered by the “top layer”. We propose a new second-order matching algorithm, which introduces no fresh free variables and just considers some selected “top layers”, arguments of the heading free variable and subterms covered by the corresponding “top layers”. A first implementation shows that the new algorithm is more efficient both in time and space than the standard one for a great number of matching problems.