论文标题
基于设置自动机匹配的术语重写
Term Rewriting Based On Set Automaton Matching
论文作者
论文摘要
在本文中，我们调查了如何利用匹配算法来实现有效的术语重写过程的。从重写系统的左侧，我们构建了一个集合的自动机，可用于有效地找到所有重新点。我们正式描述了一个程序，鉴于重写策略，它交织了模式匹配步骤和重写步骤，从而平稳整合了Redex发现和替换。然后，我们提出了有效的实现，该实现将最大的重写实例化，并介绍一些实验的结果。我们的实施表明与可比工具具有竞争力。
In this article we investigate how a subterm pattern matching algorithm can be exploited to implement efficient term rewriting procedures. From the left-hand sides of the rewrite system we construct a set automaton, which can be used to find all redexes in a term efficiently. We formally describe a procedure that, given a rewrite strategy, interleaves pattern matching steps and rewriting steps and thus smoothly integrates redex discovery and subterm replacement. We then present an efficient implementation that instantiates this procedure with outermost rewriting, and present the results of some experiments. Our implementation shows to be competitive with comparable tools.
