PYI: Characterization of Tractable Sub-Problems in Automated Reasoning

PYI：自动推理中可处理子问题的表征

• 批准号: 9157636
• 负责人: Rina Dechter
• 金额: $ 29.89万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-08-01 至 1997-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9157636&HistoricalAwards=false
• 关键词: PYI; Characterization; Tractable; Sub; Problems

This is the first year base amount funding of a five year PYI continuing award. This work will expand on the understanding and exploitation of tractable models of reasoning. To explain how people perform so well on tasks that are theoretically intractable, we must assume that approximation methods, based on tractable models, cover a significant part of intelligent activities and, hence, should serve as the cornerstone of automated reasoning systems. This principle provides the motivation for this research. This work will: (1) Establish a formal relational basis for connectionist models and neural networks and, using the language of constraint networks, quantify the powers and limitations of these models in terms of expressiveness and computational efficiency. (2) Establish a formal basis of causal theories using the language of relational algebra and (directed) constraint networks. (3) Identify tractable classes of logic programs, default knowledge bases and temporal reasoning sub-languages, recognizable via the topological features of their specifications. (4) Apply constraint network techniques to real life problems such as scheduling, planning and diagnosis.

这是保华五年期计划的首个年度基本资助额 继续获奖这项工作将扩大人们的理解， 利用易处理的推理模型。 解释如何 人们在理论上 棘手，我们必须假设近似方法，基于 易于处理的模型，涵盖了智能的重要部分， 活动，因此，应作为 自动推理系统 这一原则提供了 这项研究的动机。 本工作将：（1）建立一个 联结主义模型和神经网络的形式关系基础 网络，并使用约束网络的语言，量化 这些模型在以下方面的能力和局限性： 表现力和计算效率。 (2)建立 因果理论的形式基础，使用关系的语言 代数和（有向）约束网络。 (3)识别 易于处理的逻辑程序类，默认知识库， 时间推理子语言，可通过 其规格的拓扑特征。 (4)适用 约束网络技术到真实的生活问题，如 调度、规划和诊断。