PYI: Characterization of Tractable Sub-Problems in Automated Reasoning

点击翻译按钮获取中文摘要

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.