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

• Theoretical Computer Science • Previous Articles     Next Articles

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.

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] Zhu Mingyuan;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] Guo Hengchang;. On the Characterization and Fault Identification of Sequentially t-Diagnosable System Under PMC Model[J]. , 1991, 6(1): 83 -90 .
[3] Chen Fang; Shi Baile;. A Conservative Multiversion Locking-Graph Scheduler Algorithm[J]. , 1991, 6(2): 161 -166 .
[4] Dong Feng; Cai Wenli; Chen Tianzhou; Shi Jiaoying;. Three-Dimensional Volume Datafield Reconstruction from Physical Model[J]. , 1997, 12(3): 217 -230 .
[5] Zhao Zhuxing; Min Yinghua; Li Zhongcheng;. Path Sensitization[J]. , 1997, 12(3): 271 -282 .
[6] Chi Xuebin;. Parallel Implementation of Linear Algebra Problems on Dawning-1000[J]. , 1998, 13(2): 141 -146 .
[7] Wu Hong; Nie Xumin;. Extending STL with Efficient Data Structures[J]. , 1998, 13(4): 317 -324 .
[8] Zhou Chaochen;. An Overview of Duration Calculus[J]. , 1998, 13(6): 552 .
[9] MA Huadong; LIU Shenquan;. Multimedia Data Modeling Based on TemporalLogic and XYZ System[J]. , 1999, 14(2): 188 -193 .
[10] GU Jing; SHUAI Dianxun;. A New Parallel-by-Cell Approach to Undistorted DataCompression Based on Cellular Automatonand Genetic Algorithm[J]. , 1999, 14(6): 572 -579 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved