Computational Aspects of Normalization, Matching and Unification

标准化、匹配和统一的计算方面

• 批准号: 9303011
• 负责人: Rakesh Verma
• 金额: $ 14.41万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-06-01 至 1998-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9303011&HistoricalAwards=false
• 关键词: Computational; Aspects; Normalization; Matching; Unification

Normalization, matching, and unification are three computational steps found in virtually all symbolic computation systems. Applications of these operations include term rewriting, functional, equational and logic programming languages, abstract data type specification and verification, automated deduction, code generation, type inferencing, and computer algebra. This project addresses these problems in computing and the means to design and analyze efficient algorithms for them. Practical algorithms are designed on both sequential and parallel machines. Algorithms which learn efficiently from their history are designed for normalization with respect to several important and useful classes of rewrite systems. Several facets of matching and unification problems are studied from a novel perspective. Algorithms that correlate information from previous match/unify operations are designed for tree pattern matching and its interpreted versions, and subterm unification and its interpreted versions. The practical performance of these algorithms is investigated. This research is useful in enhancing the efficiency of symbolic systems as well as provide understanding of the inherent complexities of these operations.

规范化、匹配化、统一化是三个 在几乎所有的符号中发现的计算步骤 计算系统。 这些操作的应用包括项重写， 函数、等式和逻辑程序设计语言，抽象数据类型 规格说明与验证，自动演绎，代码生成，类型 推理和计算机代数。 该项目解决了这些问题， 计算和设计的手段和分析有效 算法对他们来说 实用算法的设计上都顺序和 平行机器 从历史中有效学习的算法是 针对几个重要和有用的 重写系统的类。 匹配与统一的几个方面 从一个新的角度研究问题。 相关算法 来自先前匹配/统一操作信息被设计用于树模式 匹配及其解释版本，以及子项统一及其解释版本。 翻译版本。 这些算法的实际性能是 研究了 该研究对于提高符号化的效率具有一定的参考价值 系统，并提供对固有的 这些操作的复杂性。