›› 2013,Vol. 28 ›› Issue (2): 278-284.doi: 10.1007/s11390-013-1329-1

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

可计算逻辑中分支切换复用运算

Mei-Xia Qu1,2 (曲美霞), Jun-Feng Luan1 (栾峻峰), Da-Ming Zhu1* (朱大铭), and Meng Du2 (杜猛)   

  • 收稿日期:2012-07-04 修回日期:2012-12-11 出版日期:2013-03-05 发布日期:2013-03-05

On the Toggling-Branching Recurrence of Computability Logic

Mei-Xia Qu1,2 (曲美霞), Jun-Feng Luan1 (栾峻峰), Da-Ming Zhu1* (朱大铭), and Meng Du2 (杜猛)   

  1. 1 School of Computer Science and Technology, Shandong University, Jinan 250101, China;
    2 School of Mechanical, Electrical and Information Engineering, Shandong University at Weihai, Weihai 264209, China
  • Received:2012-07-04 Revised:2012-12-11 Online:2013-03-05 Published:2013-03-05
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61070019 and the Natural Science Foundation of Shandong Province of China under Grant No. ZR2010FM032.

PDF (PC)

1689

论文引入了可计算逻辑中分支切换复用运算的一个简单定义, 证明了该定义与Japaridze给出的旧定义等价。同时, 论文证明了新旧两个定义给出的运算均为静态的。

Abstract: We introduce a new, substantially simplified version of the toggling-branching recurrence operation of computability logic, prove its equivalence to Japaridze's old, "canonical" version, and also prove that both versions preserve the static property of their arguments.

[1] Japaridze G. Introduction to computability logic. Annals ofPure and Applied Logic, 2003, 123(1/3): 1-99.

[2] Bauer M S. A PSPACE-complete first order fragment of com-putability logic. http://arxiv.org/abs/1201.4856, Jan. 2012.

[3] Japaridze G. Computability logic: A formal theory of inter-action. In Interactive Computation: The New Paradigm,Goldin D, Smolka S A, Wegner P (eds.), Springer, 2006,pp.183-223.

[4] Japaridze G. In the beginning was game semantics. In Games:Unifying Logic, Language, and Philosophy, Majer O, Pietari-nen A V, Tulenheimo T (eds.), Springer, 2009, pp.249-350.

[5] Japaridze G. Many concepts and two logics of algorithmicreduction. Studia Logica, 2009, 91(1): 1-24.

[6] Japaridze G. Toggling operators in computability logic. The-oretical Computer Science, 2011, 412(11): 971-1004.

[7] Japaridze G. A new face of the branching recurrence of com-putability logic. Applied Mathematics Letters, 2012, 25(11):1585-1589.

[8] Japaridze G. The taming of recurrences in computability logicthrough cirquent calculus, Part I. Archive for MathematicalLogic, 2013, 52(1/2): 173-212.

[9] Japaridze G. The taming of recurrences in computability logicthrough cirquent calculus, Part II. Archive for MathematicalLogic, 2013, 52(1/2): 213-259.

[10] Kwon K, Hur S. Adding sequential conjunctions to Prolog. J.Compu. Tech. and Applicat., 2010, 1(1): 1-3.

[11] Mezhirov I, Vereshchagin N. On abstract resource semanticsand computability logic. Journal of Computer and SystemSciences, 2010, 76(5): 356-372.

[12] Xu W Y, Liu S Y. The countable versus uncountable branch-ing recurrences in computability logic. Journal of AppliedLogic, 2012, 10(4): 431-446.

[13] Xu W Y, Liu S Y. The parallel versus branching recurrencesin computability logic. Notre Dame Journal of Formal Logic,2013, 54(1): 61-78.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 朱明远;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] 郭恒昌;. On the Characterization and Fault Identification of Sequentially t-Diagnosable System Under PMC Model[J]. , 1991, 6(1): 83 -90 .
[3] 陈昉; 施伯乐;. A Conservative Multiversion Locking-Graph Scheduler Algorithm[J]. , 1991, 6(2): 161 -166 .
[4] 董峰; 蔡文立; 陈天洲; 石教英;. Three-Dimensional Volume Datafield Reconstruction from Physical Model[J]. , 1997, 12(3): 217 -230 .
[5] 赵著行; 闵应骅; 李忠诚;. Path Sensitization[J]. , 1997, 12(3): 271 -282 .
[6] 迟学斌;. Parallel Implementation of Linear Algebra Problems on Dawning-1000[J]. , 1998, 13(2): 141 -146 .
[7] 吴虹; 聂旭民;. Extending STL with Efficient Data Structures[J]. , 1998, 13(4): 317 -324 .
[8] 周巢尘;. An Overview of Duration Calculus[J]. , 1998, 13(6): 552 .
[9] 马华东; 刘慎权;. Multimedia Data Modeling Based on TemporalLogic and XYZ System[J]. , 1999, 14(2): 188 -193 .
[10] 顾静; 帅典勋;. A New Parallel-by-Cell Approach to Undistorted DataCompression Based on Cellular Automatonand Genetic Algorithm[J]. , 1999, 14(6): 572 -579 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：