计算机科学 ›› 2015, Vol. 42 ›› Issue (7): 44-47.doi: 10.11896/j.issn.1002-137X.2015.07.010
李兴香 栾峻峰
LI Xing-xiang LUAN Jun-feng
摘要： 可计算性(Computability)即算法有解性,是数学和计算机科学领域中重要的概念之一。可计算性逻辑(Computability Logic,CoL)是关于可计算性的形式理论,是一种交互的资源逻辑。其中,CoL2系统采用博弈的语义,是对经典命题逻辑的扩展,在经典命题逻辑的基础上添加了选择运算和一般原子,比经典命题逻辑更富有表达力,具有更广阔的应用前景,并且有较高的证明效率。分析了CoL2系统的可判定性,即通过提出一个算法来判断任意一个CoL2公式是否是可证明的,并且证明了该算法是多项式空间内运行的。
| [1] Japaridze G.Introduction to computability logic[J].Annals ofPure and Applied Logic,2003,123:1-99 [2] Japaridze G.Propositional computability logic I[J].ACM Tran-sactions on Computational Logic,2006,7(2):302-330 [3] Japaridze G.Propositional computability logic II[J].ACMTransactions on Computational Logic,2006,7(2):331-362 [4] Japaridze G.Computability logic:a formal theory of interaction.Interactive Computation:TheNew Paradigm[C]∥Goldin D,Smolka S,Wegner P,eds.Springer Verlag,Berlin,2006:183-223 [5] Japaridze G.From truth to computability I[J].Theoretical Computer Science,2006,357:100-135 [6] Japaridze G.From truth to computability II[J].TheoreticalComputer Science,2007,379:20-52 [7] Japaridze G.In the beginning was game semantics.Games:Unifying Logic,Language and Philosophy[C]∥Majer O,Pietarinen A-V,Tulenheimo T,eds.Springer,2009:249-350 [8] Japaridze G.The propositional logic of elementary tasks[J].Notre Dame Journal of Formal Logic,2000,41(2):171-183 [9] Sipser M.Introduction to the Theory of Computation[M].Thompson,2006 [10] Xu W,Liu S.Deduction theorem for symmetric cirquent calculus[J].Advances in Intelligent and Soft Computing,2010,82:121-126 [11] Blass A.A game semantics for linear logic[J].Annals of Pure and Applied Logic,1992,56:183-220 [12] 朱大铭,马绍汉.算法分析与设计[M].北京:高等教育出版社,2009 Zhu Da-ming,Ma Shao-han.Design and Analysis of Algorithms[M].Beijing:Higher education press,2009 |
| No related articles found! |
|
||
首页