期刊文献+

部分蕴涵复杂性分析

Complexity Analysis of Partial Implication Semantics
原文传递
导出
摘要 极小模型和部分蕴涵语义在人工智能很多领域中有着广泛的应用.本文分析当前件和后件分别是文字、文字集和公式时,极小模型和部分蕴涵语义的复杂性问题并做相关讨论.结果表明,随着前件和后件越复杂,相关的判定问题复杂度越高.而这些判定问题的复杂度都在多项式谱系的前两层之内. Minimal model and partial implication semantics play important roles in the sub-fields of artificial intelligence. In this paper, the complexity issues of minimal model and partial implication semantics are analyzed when the antecedent and the consequent are literals, literal sets and formulas respectively. The results show that the complexities of minimal model and partial implication semantics increase when the antecedent and consequent become more complex. Moreover, the complexities of all these decision problems lie in the first two layers of polynomial hierarchy.
作者 周熠 陈小平
出处 《模式识别与人工智能》 EI CSCD 北大核心 2007年第5期593-598,共6页 Pattern Recognition and Artificial Intelligence
基金 国家自然科学基金项目(No.60275024) 国家973计划项目(No.2003CB317000)资助
关键词 计算复杂性 极小模型 部分蕴涵 人工智能 Complexity Analysis, Minimal Model, Partial Implication, Artificial Intelligence
  • 相关文献

参考文献13

  • 1van der Hoek W, Wooldrige W. Towards a Logic of Rational Agency. Logic Journal of the IGPL, 2003, 11(2): 133-157.
  • 2胡山立,fzu.edu.cn,石纯一.Agent的意图模型[J].软件学报,2000,11(7):965-970. 被引量:24
  • 3毛新军,王怀民,陈火旺,刘凤歧.Agent在多Agent系统中计算的意愿理论[J].软件学报,1999,10(1):43-48. 被引量:9
  • 4Rao A S, Georgeff M P. Modeling Rational Agents within a BDI-Architecture// Proc of the 2nd International Conference on Principles of Knowledge Representation and Reasoning. San Mateo, USA: Morgan Kaufmann, 1991:473-484.
  • 5Zhao Xinyu, Lin Zuoquan. Modeling Belief, Capability and Promise for Cognitive Agents-A Modal Logic Approach // Proc of the 1st International Conference on Natural Computation. Changsha, China, 2005:825-834.
  • 6Lang J, l.iberatore P, Marquis P. Propositional Independence - Formula-Variable Independence and Forgetting. Journal of Artificial Intelligence Research. 2003, 18:391-443.
  • 7Lakemeyer G. Relevance from an Epistemic Perspective. Artificial Intelligence, 1997, 97(1/2): 137-167.
  • 8Marquis P. Novelty Revisited // Proc of the 6th International Symposium on Methodologies for Intelligent System. Charlotte, USA, 1991:550-559.
  • 9Eiter T, Gottlob G. The Complexity of Logic-Based Abduction. Journal of ACM, 1995, 42(1): 3-42.
  • 10陈荣,姜云飞,林笠.溯因推理研究:现状与问题[J].计算机科学,2003,30(5):23-25. 被引量:6

二级参考文献15

  • 1Rao A S,Principles of Knowledge Representation and Reasoning. Proceedings of the 2 nd In,1991年,473页
  • 2Rao A S,Proceedings of the12 th International Joint Conference on Artificial Intelligenc,1991年,498页
  • 3Rao AS, Georgeff MP. Modeling rational agents within a BDI-architecture. In: Allen J, et al, eds. Proc. of the 2nd Int'l Conf.(KR'91). San Mareo: Morgan Kaufmann Publishers, Inc., 1991. 473-484.
  • 4Herzig A, Longin D. C & L intention revised. In: Dubois D, et al. eds. Proc. of the 9th Int'l Conf (KR 2004). Menlo Park: AAAI Press, 2004. 527-535.
  • 5Chen XP, Liu GQ. A logic of intention. In: Dean T, ed. Proc. of the IJCAI'99. San Mateo: Morgan Kaufmann Publishers, Inc., 1999172-177.
  • 6Georgeff M, Pell B, Pollack M, Tambe M, Wooldridge M. The belief desire intention model of agency. In: Muller J, et al, eds. Proc.of the Agents, Theories, Architectures and Languages (ATAL'98). Heidelberg: Springer-Verlag, 1998. 1-10.
  • 7Weld. DS. Recent advances in AI planning. AI Magazine, 1999,20(2):93-123.
  • 8Zhou Y, Chen XP. Partial implications semantics for desirable propositions. In: Dubois D, et al. eds. Proc. of the 9th Int'l Conf.(KR 2004). Menlo Park: AAAI Press, 2004. 606-611.
  • 9Doyle J, Thomason R. Background to qualitative decision theory. AI-Magazine, 1999,20(2):55-68.
  • 10Lang J, van der Torre L, Weydert E. Hidden uncertainty in the logical representation of desires. In: Gottlob T, Walsh T, eds. Proc.of the IJCAI 2003. Acapulco: Morgan Kaufmann Publishers, 2003. 685-690.

共引文献35

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部