Computational Aspects of Rewriting

术语重写系统是程序设计语言、抽象数据类型说明与验证、自动演绎和计算机代数等领域的重要计算范式。改写理论发展迅速，新的应用领域不断被探索。然而，对于重写操作的计算方面，我们了解的并不多。在本提案中，将研究重写的基本操作，以及设计和分析有效算法的方法。将在顺序机和并行机上设计实用的算法。从历史中有效学习的算法将被设计用于重要和有用的重写系统类。本文将从一个全新的视角来研究匹配问题的几个方面。本文还将研究所设计算法的实际性能。这项研究将有助于提高基于重写的系统的效率，并提供对重写方法固有复杂性和局限性的理解。

Term rewriting systems form an important computational paradigm in programming languages, abstract data type specification and verification, automated deduction and computer algebra. The theory of rewriting has developed rapidly, and new application areas are being explored. However, not much is known about the computational aspects of rewrite operations. In this proposal the basic operations in rewriting, and the means to design and analyze efficient algorithms for them, will be studied. Practical algorithms will be designed on both sequential and parallel machines. Algorithms, which learn efficiently from their history, will be designed for important and useful classes of rewrite systems. Several facets of the matching problem will be studied from a novel perspective. The practical performance of the designed algorithms will also be investigated. This investigation will be useful in improving the efficiency of rewrite-based systems as well as provide understanding of the inherent complexities and limitations of the rewrite approach.