Computability Logic: Literature

Computability Logic

(CoL)

Home Contents

Literature

Section 9

Literature

9.1 Selected papers on CoL by Japaridze

9.2 Selected papers on CoL by other authors

9.3 PhD theses, MS theses and externally funded projects on CoL

9.4 Lecture notes on CoL, presentations and other links

9.5 Additional references

9.1 Selected papers on CoL by Japaridze

• [Jap03] G.Japaridze. Introduction to computability logic . Annals of Pure and Applied Logic 123 (2003), pp.1-99. Preprint Erratum.

• [Jap06a] G.Japaridze. Propositional computability logic I . ACM Transactions on Computational Logic 7 (2006), No. 2, pp. 302-330. Preprint

• [Jap06b] G.Japaridze. Propositional computability logic II . ACM Transactions on Computational Logic 7 (2006), No. 2, pp. 331-362. Preprint

• [ Jap06c] G.Japaridze. Introduction to cirquent calculus and abstract resource semantics . Journal of Logic and Computation 16 (2006), No.4, pp. 489-532. Preprint

• [Jap06d] G.Japaridze. Computability logic: a formal theory of interaction . In: Interactive Computation: The New Paradigm . D.Goldin, S.Smolka and P.Wegner, eds. Springer 2006, pp. 183-223. Preprint

• [Jap06e] G.Japaridze. From truth to computability I. Theoretical Computer Science 357 (2006), pp. 100-135. Preprint

• [ Jap07a] G.Japaridze. From truth to computability II . Theoretical Computer Science 379 (2007), pp. 20-52. Preprint

• [ Jap07b] G.Japaridze. Intuitionistic computability logic . Acta Cybernetica 18 (2007), No.1, pp.77-113. Preprint

• [Jap07c] G.Japaridze. The logic of interactive Turing reduction. Journal of Symbolic Logic 72 (2007), No.1, pp. 243-276. Preprint

• [ Jap07d] G.Japaridze. The intuitionistic fragment of computability logic at the propositional level . Annals of Pure and Applied Logic 147 (2007), No.3, pp.187-227. Preprint

• [ Jap08a] G.Japaridze. Cirquent calculus deepened . Journal of Logic and Computation 18 (2008), No.6, pp.983-1028.

• [ Jap08b] G.Japaridze. Sequential operators in computability logic . Information and Computation 206 (2008), No.12, pp. 1443-1475. Preprint

• [Jap09a] G.Japaridze. In the beginning was game semantics . In: Games: Unifying Logic, Language and Philosophy. O. Majer, A.-V. Pietarinen and T. Tulenheimo, eds. Springer 2009, pp.249-350. Preprint

• [ Jap09b] G.Japaridze. Many concepts and two logics of algorithmic reduction . Studia Logica 91 (2009), No.1, pp. 1-24. Preprint

• [ Jap10] G.Japaridze. Towards applied theories based on computability logic . Journal of Symbolic Logic 75 (2010), pp. 565-601. Preprint

• [ Jap11a] G.Japaridze. Toggling operators in computability logic . Theoretical Computer Science 412 (2011), pp. 971-1004. Preprint

• [ Jap11b] G.Japaridze. From formulas to cirquents in computability logic .Logical Methods in Computer Science 7[2:1] (2011), pp. 1-55.

• [ Jap11c] G.Japaridze. Introduction to clarithmetic I . Information and Computation 209 (2011), pp. 1312-1354. Preprint

• [ Jap12a] G.Japaridze. Separating the basic logics of the basic recurrences . Annals of Pure and Applied Logic 163 (2012), pp. 377-389. Preprint

• [ Jap12b] G.Japaridze. A new face of the branching recurrence of computability logic . Applied Mathematics Letters 25 (2012), pp. 1585-1589. Preprint

• [ Jap12c] G.Japaridze. A logical basis for constructive systems . Journal of Logic and Computation 22 (2012), pp.605-642.

• [ Jap13a] G.Japaridze. The taming of recurrences in computability logic through cirquent calculus, Part I. Archive for Mathematical Logic 52 (2013), pp. 173-212. Preprint

• [ Jap13b] G.Japaridze. The taming of recurrences in computability logic through cirquent calculus, Part II. Archive for Mathematical Logic 52 (2013), pp. 213-259. Preprint

• [ Jap14] G.Japaridze.Introduction to clarithmetic III . Annals of Pure and Applied Logic 165 (2014), pp. 241-252. Preprint

• [ Jap15] G.Japaridze. On the system CL12 of computability logic. Logical Methods in Computer Science 11[3:1] (2015), Issue 3, pp.1-71.

• [ Jap16a] G.Japaridze. Introduction to clarithmetic II . Information and Computation 247 (2016), pp.290-312. Preprint

• [ Jap16b] G.Japaridze. Build your own clarithmetic I: Setup and completeness . Logical Methods in Computer Science 12[3:8] (2016), pp. 1-59.

• [ Jap16c] G.Japaridze. Build your own clarithmetic II: Soundness. Logical Methods in Computer Science 12[3:12] (2016), pp. 1-62.

• [Jap18] G.Japaridze. Elementary-base cirquent calculus I: Parallel and choice connectives. Journal of Applied Logics - IfCoLoG Journal of Logics and their Applications 5 (2018), no.1, pp. 367-388. Preprint

ƒL ?[Jap19a] G.Japaridze. Computability logic: Giving Caesar what belongs to Caesar. Logical Investigations 25 (2019), No.1, pp. 100-119. Preprint

• [Jap19b] G.Japaridze. Arithmetics based on computability logic. Logical Investigations 25 (2019), No.2, pp. 61-74.
• [Jap20a] G.Japaridze. Elementary-base cirquent calculus II: Choice quantifiers . Logic Journal of the IGPL 29 (2021), pp. 769-782. [SCI]
  Official journal version Online preprint
• [Jap20b] G.Japaridze. Fundamentals of computability logic 2020.
  Journal of Applied Logics - IfCoLoG Journal of Logics and their Applications 7 (2020), pp. 1115-1177. [SCI]
  Official journal version Online preprint

ƒL G.Japaridze, B.Lamichhane.Cirquent calculus in a nutshell.
Logical Investigations 2022, Vol. 28, No. 1. Pages 9?24.
Official journal version ???? Online preprint

ƒL G.Japaridze. Fundamentals of computability logic. In: Selected Topics from Contemporary Logic . Melvin Fitting, ed. 2021,? pp. 477-537.

?????? Official book version???? Online preprint

ƒL G.Japaridze. ?A propositional cirquent calculus for computability logic. ?Journal of Logic, Language and Information 33 (2024), pp. 363-389 [SCI]

?????? Official journal version ???? Online preprint

ƒL G.Japaridze. Thoughts on sub-Turing interactive computability. Logical Investigations 2025 (to appear)
?????? Official journal version??? ?Online preprint

9.2 Selected (SCI-indexed) papers on CoL by other authors

• [ Bau14] M.Bauer.A PSPACE-complete first order fragment of computability logic. ACM Transactions on Computational Logic 15 (2014), No 1, Article 1, 12 pages.

• [Bau15] M.Bauer.The computational complexity of propositional cirquent calculus. Logical Methods is Computer Science 11[1:12] (2015), pp.1-16.

• [Kwo14] K.Kwon. Expressing algorithms as concise as possible via computability logic.IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , vol. E97-A (2014), pp.1385-1387.

• [Mez10] I.Mezhirov and N.Vereshchagin. On abstract resource semantics and computability logic. Journal of Computer and Systems Sciences 76 (2010), pp. 356-372.

• [Qu13] M.Qu, J.Luan, D.Zhu and M.Du.On the toggling-branching recurrence of computability logic . Journal of Computer Science and Technology 28 (2013), pp. 278-284.

• [Xu12a] W.Xu and S.Liu.The countable versus uncountable branching recurrences in computability logic . Journal of Applied Logic 10 (2012), pp. 431-446.

• [Xu12b] W.Xu and S.Liu. Soundness and completeness of the cirquent calculus system CL6 for computability logic . Logic Journal of the IGPL 20 (2012), pp. 317-330.

• [ Xu13] W.Xu and S.Liu. The parallel versus branching recurrences in computability logic. Notre Dame Journal of Formal Logic 54 (2013), pp. 61-78.

• [ Xu14] W.Xu.A propositional system induced by Japaridze’s approach to IF logic . Logic Journal of the IGPL 22 (2014), pp. 982-991.

• [ Xu16] W.Xu.A cirquent calculus system with clustering and ranking. Journal of Applied Logic 16 (2016), pp.37-49.

9.3 PhD theses, MS theses and externally funded projects on CoL

• S.Spadoni. The Fertile Steppe: Computability Logic and the decidability of one of its fragments . MS Thesis. University of Florence, 2025.
• M.Qu. Research on the toggling-branching recurrence of Computability Logic . PhD Thesis. Shandong University, 2014.

• Y.Zhang. Time and Space Complexity Analysis for the System CL2 of Computability Logic . MS Thesis. Shandong University, 2013.

• W.Xu. On Some Operators and Systems of Computability Logic . PhD Thesis. Xidian University, 2012.

• W.Xu. A Study of Cirquent Calculus Systems for Computability Logic. Research project funded by the National Science Foundation of China (61303030) and the Fundamental Research Funds for the Central Universities of China (K50513700). Xidian University, 2013-2016.

• G.Japaridze. A Logical Study of Interactive Computational Problems Understood as Games. Research project funded by the National Science Foundation of US (CCR-0208816). Villanova University, 2002-2006.

9.4 Lecture notes, presentations and other links

• Giorgi Japaridze: Research and Publications
• A list of open problems in CoL
• LaTeX macros for the operators of CoL
• Graduate course on CoL (taught in 2018 at Southwest University, China. Includes lecture notes in PowerPoint)
• Graduate course on CoL (taught in 2007 at Xiamen University, China. Includes lecture notes in PowerPoint)
• Three-hour tour of CoL (PowerPoint slides)
• Four-hour tour of CoL (PowerPoint slides)
• On abstract resource semantics and computabilty logic (video lecture by N.Vereshchagin)
• Strong alternatives to weak arithmetics (video lecture by Japaridze, 2017)
• Computability logic: Giving Caesar what belongs to Caesar (video lecture by Japaridze in Russian, 2017)
• Arithmetic based on computability logic (video lecture by Japaridze, 2018)
• Proofs as games
• Computability logic-1
• Lambda the Ultimate: Introduction to computability logic
• Lambda the Ultimate: In the beginning was game semantics

9.5 Additional references

• [ Abr94] S. Abramsky and R. Jagadeesan. Games and full completeness for multiplicative linear logic. Journal of Symbolic Logic 59 (2) (1994), pp. 543-574.
• [ Avr87] A. Avron. A constructive analysis of RM. Journal of Symbolic Logic 52 (1987), pp. 939-951.
• [Bla72] A. Blass. Degrees of indeterminacy of games. Fundamenta Mathematicae 77 (1972), pp. 151-166.
• [ Bla92] A. Blass. A game semantics for linear logic. Annals of Pure and Applied Logic 56 (1992), pp 183-220.
• [ Bus86] S. Buss. Bounded Arithmetic (revised version of Ph. D. thesis). Bibliopolis, 1986.
• [ Cha81] A. Chandra, D. Kozen and L. Stockmeyer. Alternation. Journal of the ACM 28 (1981), pp. 114-133.
• [ Clo92] P. Clote and G. Takeuti. Bounded arithmetic for NC, ALogTIME, L and NL. Annals of Pure and Applied Logic 56 (1992), pp. 73-117.
• [ Coo10] S. Cook and P. Nguyen. Logical Foundations of Proof Complexity. Cambridge University Press, 2010.
• [ Fel85] W. Felscher. Dialogues, strategies, and intuitionistic provability. Annals of Pure and Applied Logic 28 (1985), pp. 217-254.
• [ Gir87] J.Y. Girard. Linear logic. Theoretical Computer Science 50 (1) (1987), pp. 1-102.
• [Goe58] K. Goedel. Ueber eine bisher noch nicht benuezte Erweiterung des finiten Standpunktes. Dialectica 12 (1958), pp. 280-287.
• [ Gol06] D. Goldin, S. Smolka and P. Wegner (editors). Interactive Computation: The New Paradigm. Springer, 2006.
• [ Gol89] S. Goldwasser, S. Micali and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18 (1989), pp. 186-208.
• [ Gug07] A. Guglielmi. A system of interaction and structure. ACM Transactions on Computational Logic 8 (2007), No.1, pp. 1-64.
• [ Haj93] P. Hajek and P. Pudlak. Metamathematics of First-Order Arithmetic. Springer, 1993.
• [ Hey71] A. Heyting. Intuitionism: An Introduction. Amsterdam, North-Holland Publishing, 3rd revised edition, 1971.
• [ Hin73] J. Hintikka. Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic. Clarendon Press 1973.
• [ Hin97] J. Hintikka and G. Sandu. Game-theoretical semantics. In: Handbook of Logic and Language. J. van Benthem and A ter Meulen, eds. North-Holland 1997, pp. 361-410.
• [ Kle52] S.C. Kleene. Introduction to Metamathematics. D. van Nostrand Company, New York / Toronto, 1952.
• [ Kra95] J. Krajicek. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press, 1995.
• [ Lor61] P. Lorenzen. Ein dialogisches Konstruktivitƒe�Atskriterium. In: Infinitistic Methods. In: PWN, Proc. Symp. Foundations of Mathematics, Warsaw, 1961, pp. 193-200.
• [ Par71] R. Parikh. Existence and feasibility in arithmetic. Journal of Symbolic Logic 36 (1971), pp. 494-508.
• [ Par85] J. Paris and A. Wilkie. Counting problems in bounded arithmetic. In: Methods in Mathematical Logic. Lecture Notes in Mathematics No. 1130. Springer, 1985, pp. 317-340.
• [ Sch06] H. Schwichtenberg. An arithmetic for polynomial-time computation. Theoretical Computer Science 357 (2006), pp. 202-214.