Computational Aspects of Rewrite Operations

近年来，术语重写系统作为编程语言、自动演绎、数据类型规范和验证、计算机代数的方便工具，以及作为逻辑和编程之间的桥梁，受到了相当大的关注。术语改写理论发展迅速，新的应用领域不断被探索。然而，对于重写操作的计算方面，人们似乎知之甚少。本文提出了与重写相关的基本操作，以及设计和分析相关算法的方法。实际算法和下界复杂性，在顺序和并行机器，将进行研究。为重写操作设计好的算法的研究将有助于提高基于重写的系统的效率，并提供对重写方法固有复杂性和局限性的理解。

Term rewriting systems have gained considerable attention in recent years for being a convenient tool in programming languages, automated deduction, data type specification and verification, computer algebra, and as a bridge between logic and programming. The theory of term rewriting has developed rapidly and new areas of applications are being explored. However, not much seems to be known about the computational aspects of rewrite operations. This proposal addresses the basic operations that are pertinent to rewriting and the means to design and analyze the associated algorithms. Both practical algorithms and lower bound complexities, on sequential and parallel machines, will be studied. Research in the design of good algorithms for rewrite operations will be useful in improving the efficienty of rewrite-based systems as well as in providing an understanding into the inherent complexities and limitations of rewrite methods.