Computational Aspects of Rewriting

重写的计算方面

• 批准号: 9010366
• 负责人: Rakesh Verma
• 金额: $ 3.61万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-09-01 至 1993-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9010366&HistoricalAwards=false
• 关键词: Computational; Aspects; 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.

项重写系统是一种重要的计算范式， 编程语言、抽象数据类型规范和 验证、自动演绎和计算机代数。 理论 重写发展迅速，新的应用领域正在开发中。 探讨了 然而，对计算方面知之甚少 重写操作。 在本提案中， 重写，以及设计和分析有效算法的方法 他们将被研究。 实用算法将在 包括顺序和并行机器。 从历史中有效学习的算法， 为重要和有用的重写系统类而设计。 几 匹配问题的各个方面将从一个新的研究 perspective. 所设计算法的实际性能 也将受到调查。这项调查将有助于 提高基于重写的系统的效率，以及提供 理解的内在复杂性和局限性， 重写方法。