Towards Tractable Reasoning on Temporal Projection Problems
It is well known that reasoning with AI temporal projection problems is difficult. Determining the Possible Truth problem, a basic temporal projection decision problem, in the so-called Simple Event System remains NP-complete. In this paper, two types of constraints, on the graph-theoretic representation of the cause-and-effect relationships between events and on the partial orders of events, are further considered upon this boundary NP-complete Possible Truth problem, in an attempt to gain tractability. In particular, we show that the problem is still NPcomplete even if the cause-and-effect graphs maintain a strongly restricted topology, whereas it is tractable if the graph is closely associated with the set of pairwise disjoint partial orders, which in addition is hierarchically structured.
Xing Tan Michael Gruninger
Semantic Technologies Laboratory Department of Mechanical and Industrial Engineering University of Toronto
国际会议
上海
英文
723-727
2009-11-20（万方平台首次上网日期，不代表论文的发表时间）