Giorgi Japaridze
Research and
Publications

NOTE:
Before 1994 the English spelling of my name was "Dzhaparidze",
the result of a two-step transliteration Georgian -> Russian -> English,
while the current "Japaridze" is a direct transliteration from
Georgian into English. Don't get confused if you need to look up my name in
some earlier literature.
Main Contributions to Science
Provability
and interpretability logics
(1985-1998)
·
While a student, introduced polymodal
provability logic GLP,
and proved its arithmetical completeness. This contained a solution of an open
problem on the logic of w-provability
raised by George Boolos a decade earlier (1985-1988).
·
Introduced logic D and proved its
arithmetical completeness (1987).
·
Extended Solovay's theorems
from propositional level to the one-variable predicate level, and introduced
the corresponding sound and complete logic GLq
(1987).
·
Introduced the concepts of cointerpretability,
tolerance
and cotolerance (1992-1993).
·
Proved that cointerpretability
is equivalent to S1-conservativity
and tolerance is equivalent to P1-consistency.
This was an answer to the long-standing open problem regarding the metamathematical meaning of S1-conservativity
(1992-1993).
·
Introduced modal logics for tolerance and proved
their arithmetical completeness (1993).
·
Introduced a modal logic for the arithmetical
hierarchy and proved its arithmetical completeness (1994).
Game
semantics and the theory of interactive computation
(1997-present)
·
Introduced the Logic of Tasks (2000-2002). It
later became a part of computability logic on one hand, and a part of abstract
game semantics on the other hand.
·
Introduced and started elaborating Computability
Logic. This is work with a beginning but no end. An
ambitious program and platform for redeveloping logic as a formal theory of
(interactive) computability, as opposed to the formal theory of truth that it
has more traditionally been (2003-2007).
·
Proved the soundness and completeness of intuitionistic
logic with respect to the semantics of computability logic, thus corroborating
Kolmogorov's (1932) well known yet rather abstract thesis, according to which
intuitionistic logic is a logic of problems
(2006-2007).
·
Introduced Abstract Resource Semantics
(2006).
Proof
theory and deep inference
(2006-present)
- Introduced the new proof-theoretic framework called Cirquent Calculus (2006-2007).
Complexity
theory
(2010-present)
- Introduced Clarithmetics --- computability-logic-based formal arithmetics for various computational complexity
classes.
Publications
- G.Japaridze,
Introduction to clarithmetic III
Annals
of Pure and Applied Logic (to appear)
Official
journal version
Online preprint
- G.Japaridze,
The taming of recurrences in computability logic through cirquent calculus, Part II
Archive for Mathematical Logic 52 (2013), pp. 213-259.
Official
journal version
Online preprint Authors
official copy
- G.Japaridze,
The taming of recurrences in computability logic through cirquent calculus, Part I
Archive for Mathematical Logic 52 (2013), pp. 173-212.
Official
journal version
Online preprint Authors
official copy
- G.Japaridze,
A new face of the branching recurrence of computability logic
Applied Mathematics Letters 25
(2012), pp. 1585-1589.
Official journal
version Online preprint
- G.Japaridze,
A logical basis for constructive systems
Journal of Logic and Computation 22 (2012), pp. 605-642.
Official
journal version (free access)
- G.Japaridze,
Separating the basic logics of the basic recurrences
Annals
of Pure and Applied Logic 163 (2012), pp. 377-389.
Official journal
version Online preprint
- G.Japaridze,
Introduction to clarithmetic I
Information and Computation 209 (2011), pp.
1312-1354.
Official journal version Online preprint
- G.Japaridze,
From formulas to cirquents in computability
logic
Loical
Methods is Computer Science 7 (2011), Issue
2 , Paper 1, pp. 1-55.
Official
journal version (free access)
- G.Japaridze,
Toggling operators in computability logic
Theoretical
Computer Science 412 (2011), pp. 971-1004.
Official journal
version Online preprint
- G.Japaridze,
Towards applied theories based on computability logic
Journal of Symbolic
Logic
75 (2010), pp. 565-601.
Official
journal version
Online preprint
- G.Japaridze,
Many concepts and two logics of algorithmic reduction
Studia Logica 91 (2009), No.1, pp. 1-24.
Official
journal version
Online preprint
- G.Japaridze,
In the beginning was game semantics
Games:
Unifying Logic, Language and Philosophy. O. Majer, A.-V. Pietarinen and
T. Tulenheimo, eds. Springer 2009, pp.
249-350.
Official
book version Online preprint
- G.Japaridze,
Sequential operators in computability logic
Information and Computation
206 (2008), No.12, pp. 1443-1475.
Official journal version Online preprint
- G.Japaridze,
Cirquent calculus deepened
Journal of Logic and
Computation 18 (2008), No.6, pp. 983-1028.
Official
journal version (free access)
- 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.
Official journal
version Online preprint
- G.Japaridze,
The logic of interactive Turing reduction
Journal
of Symbolic Logic 72 (2007), No.1, pp. 243-276.
Official
journal version
Online preprint
- G.Japaridze,
Intuitionistic computability logic
Acta Cybernetica
18
(2007), No. 1, pp. 77-113.
Official
journal version Online preprint
- G.Japaridze,
From truth to computability II
Theoretical
Computer Science 379 (2007), pp. 20-52.
Official journal
version Online
preprint
- G.Japaridze,
From truth to computability I
Theoretical
Computer Science 357 (2006), pp. 100-135.
Official journal
version Online
preprint
- G.Japaridze,
Introduction to cirquent calculus and
abstract resource semantics
Journal of Logic and
Computation 16 (2006), No.4, pp. 489-532.
Official
journal version
Online preprint
- G.Japaridze,
Computability logic: a formal theory of interaction
Interactive
Computation: The New Paradigm. D.Goldin,
S.Smolka and P.Wegner,
eds. Springer Verlag, Berlin 2006, pp. 183-223.
Official book
version Online preprint
- G.Japaridze,
Propositional computability logic II
ACM Transactions on
Computational Logic 7 (2006), No. 2, pp. 331-362.
Official
journal version
Online preprint
- G.Japaridze,
Propositional computability logic I
ACM Transactions on
Computational Logic 7 (2006) No.2, pp. 302-330.
Official
journal version
Online preprint
- G.Japaridze,
The simplest
completeness proof in computability logic
Vriendboek
ofwel Liber Amicorum
ter gelegenheid van
het afscheid van Dick de Jongh. Institute
for Logic, Language and Computation, University of Amsterdam, 2004. 7
pages.
- G.Japaridze,
A basic completeness theorem of CL.
Bulletin of the
Georgian Academy of Sciences 169 (2004), No.1, pp. 34-36.
- G.Japaridze,
A basic soundness theorem of CL.
Bulletin of the
Georgian Academy of Sciences 168 (2003), No.3, pp. 215-218.
- G.Japaridze,
Introduction to computability logic
Annals
of Pure and Applied Logic, vol. 123 (2003), p. 1-99.
Official
journal version
Online preprint
- G.Japaridze,
Some preliminary results on computability logic
Proceedings of Kalmar Workshop on Logic and Computer Science.
Szeged, Hungary, 2003. 15 pages.
- G.Japaridze,
What
is the real logic of games after all?
Proceedings of the 3rd and 4th International Symposium on Language,
Logic and Computation. D. De Jongh,
H.Zeevat and M Nilsenova
(EDS.). ILLCScientific Publications, Amsterdam,
2002, pp. 243-257.
- G.Japaridze,
Preliminary results on the basic predicate logic of racefree games.
Bulletin of the
Georgian Academy of Sciences 165 (2002), No. 2, pp. 256-259.
- G.Japaridze,
Preliminary results on the basic propositional logic of racefree games.
Bulletin of the
Georgian Academy of Sciences 165 (2002), No. 1, pp. 26-29.
- G.Japaridze,
The logic of tasks.
Annals
of Pure and Applied Logic 117 (2002), pp. 263-295
Official
journal version Online
preprint
- G.Japaridze,
A decidable substructural predicate logic
with a natural semantics.
4th Tbilisi Symposium on Language, Logic and Computation
(abstracts) ILLC, University of Amsterdam / CLLS, Tbilisi State
University, 2001, 5 pages.
- G.Japaridze,
A task semantics for the language of linear logic
Bulletin of the
Georgian Academy of Sciences 163, No. 1 (2001), pp. 5-7.
- G.Japaridze,
The propositional logic of elementary tasks
Notre Dame Journal of Formal Logic
41 (2000), No. 2, pp. 171-183.
Official
journal version Online preprint
- G.Japaridze,
A decidable first order epistemic logic
Proceedings of the Georgian Academy of Sciences No. 1-2
(2000), pp. 81-95.
- G.Japaridze and D.DeJongh
The logic of provability.
Handbook
of Proof Theory, S.Buss, ed.,
North-Holland, 1998, pp. 475-545.
Official book
version Online
preprint
- G.Japaridze,
A constructive game semantics for the language of linear logic.
Annals
of Pure and Applied Logic 85 (1997), No. 2, pp. 87-156.
Official
journal version Online preprint
- G.Japaridze,
A simple proof of arithmetical completeness for Pi-1 conservativity logic.
Notre Dame Journal of Formal Logic
35 (1994), No. 3. pp. 346-354.
Official
journal version Online preprint
- G.Japaridze,
The logic of the arithmetical hierarchy.
Annals
of Pure and Applied Logic 66 (1994), No. 2, pp. 89-112.
- G.Japaridze,
A generalized notion of weak interpretability and the corresponding
modal logic.
Annals
of Pure and Applied Logic 61 (1993), No. 1-2, pp. 113-160.
- G.Japaridze,
The logic of linear tolerance.
Studia
Logica 51 (1992), No. 2, pp.
249-277.
Official
journal version Online preprint
- G.Japaridze,
Predicate provability logic with non-modalized
quantifiers.
Studia
Logica 50 (1991), No. 1, pp.
149-160.
Official
journal version Online preprint
- G.Japaridze,
Semidecidable fragments of first
order provability logic.
Semantical Analysis of
Non-classical Logics. Tbilisi, Metsniereba,
1991, pp. 63-79
- G.Japaridze,
The logic of generalized weak interpretability.
Bulletin of the
Academy of Sciences of the Georgian SSR 143 (1991), No. 3,
pp. 233-235.
- G.Japaridze,
The propositional logic of truth and provability.
Logic and Philosophic Essays. Moscow, 1991, pp. 43-52
(Russian).
- G.Japaridze,
Decidable and enumerable predicate logics of provability.
Studia
Logica 49 (1990), No. 1, pp. 7-21.
Official
journal version Online preprint
- S.Artemov and G.Japaridze,
Finite Kripke models and predicate logics of
provability.
Journal
of Symbolic Logic 55 (1990), No. 3, pp. 1090-1098.
Official
journal version Online preprint
- G.Japaridze,
Provability logic with modalities for arithmetical complexities.
Bulletin of the
Academy of Sciences of the Georgian SSR 138 (1990), No. 3,
pp. 481-484.
- G.Japaridze,
On predicate provability logics of nonenumerable
theories.
Suslin Mathematical
Readings. Saratov, 1989, p. 84 (Russian).
- G.Japaridze,
The polymodal logic of provability.
Intensional Logics and
Logical Structure of Theories. Metsniereba,
Tbilisi, 1988, pp. 16-48 (Russian).
- G.Japaridze,
The arithmetical completeness of provability logic with quantifier
modalities.
Bulletin of the
Academy of Sciences of the Georgian SSR 132 (1988), No. 2,
pp. 265-268.
- G.Japaridze,
Quantifiers over realizations in provability logic.
Semiotical Aspects of
Formalization of the Intellectual Activity. Moscow, 1988, pp.
81-83 (Russian).
- G.Japaridze,
Quantifier modalities in provability logic.
Proceedings of the 9th All Union Conference on Mathematical Logic.
Leningrad, 1988, p. 51 (Russian).
- S.Artemov and G.Japaridze,
On effective predicate logics of provability.
Doklady AN SSSR (now Dokady Mathematics) 297 (1987), No. 3, pp. 521-523
(Russian).
English translation in: Soviet Math. Doklady
36, pp.478-480.
- G.Japaridze,
Generalized provability principles and modal logic.
Proceedings of the 8th International Congress on Logic, Methodology
and Philosophy of Science. Moscow, 1987, volume 5, Part 1, pp.
32-34.
- G.Japaridze and L.Mchedlishvili,
Gottlob Frege: Begriffshrift
Methods for Research in Logic, Metsniereba,
Tbilisi, 1987, pp. 83-151 (Russian).
- G.Japaridze,
Proof theory and some modal systems.
Methods of Logic Research. Tbilisi, Metsniereba,
1986, pp. 39-47 (Russian).
- G.Japaridze,
Modal logical means of studying provability
Autoreferat of the candidate's thesis. Moscow
State University, Moscow, 1986, 20 pages.
- G.Japaridze,
Some modal systems with provability interpretation of the necessity
operator.
Logic and Methods of Analysis of the Scientific Knowledge.
Moscow, 1986, pp. 18-19 (Russian).
- G.Japaridze,
GL as the intersection of truth provability logics.
Proceedings of the 8th All Union Conference on Mathematical Logic.
Moscow, 1986, p. 58 (Russian).
- G.Japaridze,
Provability principles and extensions of arithmetic.
Nonstandard Semantics of Nonclassical
Logics. Moscow, 1986, pp. 89-98 (Russian).
- G.Japaridze,
Necessity as provability.
Izvestia (Annals) of
the Academy of Sciences of the Georgian SSR (Philosophy and
Psychology), 1986, No. 3, pp. 34-44 (Russian).
- G.Japaridze,
N-provability reflected in a modal logic with infinitely many modal
operators.
Proceedings of the 4th Soviet-Finnish Symposium on Logic.
Tbilisi, 1985, pp. 56-57 (Russian).
Dissertations
- G.Japaridze,
Modal-logical Means of Studying Provability.
Ph.D. Thesis. Moscow State University, Moscow, 1987, 118
pages (Russian).
- G.Japaridze,
The Logic
of Resources and Tasks.
PhD Thesis. University of Pennsylvania, Philadelphia,
1998, 145 pages.
Research Grants
(Principal Investigator without
co-PIs)
- Outstanding Foreign Experts Program grant (China)
- Summer Research Fellowship and Grant from Villanova
University
- Project title:
"Taming recurrences in computability logic".
- Duration: Summer 2010
- Summer Research Fellowship and Grant from Villanova
University
- Project title:
"Intuitionistic computability logic".
- Duration: Summer 2005
- NSF grant CCR-0208816 (Theory of Computing Program)
- Project title: "A
logical study of interactive computational problems understood as
games".
- Duration: July 1, 2002
- June 30, 2006.
- Summer Research Fellowship from Villanova University
- Project title:
"The logic of informational games"
- Duration: Summer 1999
Major Citations
[Other authors papers focused on one of the
following 4 brainchildren of mine:
GLP (1985), Logic of Tasks (2002), Computability Logic (2003), Cirquent
Calculus (2006)]
- M.Bauer,
A PSPACE-complete
first order fragment of computability logic.
ACM
Transactions on Computational Logic (to
appear).
- L.Beklemishev and D.Gabelaia,
Topological completeness
of provability logic GLP.
Annals
of Pure and Applied Logic (to
appear)
- 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.
- W.Xu and S.Liu,
The
parallel versus branching recurrences in computability logic.
Notre Dame Journal of Formal Logic 54 (2013), pp.
61-78.
- C.Yu and W.Zhou,
Hierarchy organization model
based on the logic of tasks.
Applied
Mechanics and Materials 310 (2013), pp. 644-649.
- W.Zhang, L.Zeng and S.Li,
Coordinative
relationship model for groups organization based
on the description logic of tasks.
Computer
Engineering and Science 35:1 (2013).
- H.Kwon,
Expressing algorithms as concise as
possible via computability logic.
arXiv:1305.2004 (2013).
- W.Xu and S.Liu,
The countable versus uncountable branching recurrences in
computability logic.
Journal
of Applied Logic 10 (2012), pp. 431-446.
- 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.
- W.Xu and S.Liu,
Cirquent calculus system CL8S versus calculus of
structures system SKSg for propositional logic.
In: Quantitative
Logic and Soft Computing.
Guojun Wang, Bin Zhao and Yongming
Li, eds. Singapore, World Scientific, 2012, pp. 144-149.
- F.N. Pakhomov,
Undecidability of
the elementary theory of the semilattice of GLP-words.
Matematicheskii Sbornik 203 (2012), pp. 141-160.
- D. Fernαndez-Duque and J.J.Joosten,
Well-orders in the
transfinite Japaridze algebra.
arXiv:1212.3468 (2012).
- D. Fernαndez-Duque and J.J.Joosten,
Well-founded orders on the
transfinite Japaridze algebra II.
arXiv:1204.4743 (2012)
- W.Zhang, L.Zeng, H.Zhang
and S.Li,
Collaboration
in digital games: An approach to the description logic of tasks.
Journal
of Computer Research and Development
49:7 (2012).
- L.Beklemishev,
A
simplified proof of arithmetical completeness theorem for provability
logic GLP.
Proceedings of the Steklov Institute of Mathematics 274 (2011), pp.
25-33.
- L.Beklemishev,
Ordinal
completeness of bimodal provability logic GLB.
Lecture Notes in Computer
Science 6618 (2011), pp.
1-15.
- D.S.Shamkanov,
Interpolation
properties for provability logics GL and GLP.
Proceedings of the Steklov Institute of Mathematics 274 (2011), pp.
303-316.
- L.Min, Y.Liu and X.Chen,
Analysis
of deterministic finite automata in computability logic.
Journal
of Chongqing University of Posts and Telecommunications (Natural Science
Edition) 23:6 (2011), pp. 80-82.
- X.Ma,
On theorems in system CL4 of computability logic.
Journal of Xian Institute of Posts and Telecommunications 16:5 (2011), pp. 80-82.
- I.Mezhirov and N.Vereshchagin,
On
abstract resource semantics and computability logic.
Journal
of Computer and Systems Sciences 76 (2010), pp. 356-372.
- L.Beklemishev,
Kripke semantics for provability logic GLP.
Annals
of Pure and Applied Logic 161, 756774 (2010).
- L.Beklemishev, G. Bezhanishvili
and T. Icar,
On topological models of GLP.
Ways of proof theory, Ontos Mathematical Logic, 2,
eds. R. Schindler, Ontos Verlag, Frankfurt, 2010, pp. 133153.
- L.Beklemishev,
On the Craig interpolation and the fixed point properties of GLP.
In: Proofs, Categories and Computations. S. Feferman et al., eds., College Publications 2010. pp. 49-60.
- W.Xu and S.Liu,
Deduction
theorem for symmetric cirquent calculus.
Advances in Intelligent
and Soft Computing 82 (2010), pp.
121-126.
- W.Zhang, L.Zeng, H.Zhang and S.Li,
Task planning
based on the description logic of tasks in joint operation scenarios.
Journal
of Software 21
(2010), pp.140−148.
- W.Xu and S.Liu,
Knowledge
representation and reasoning rased on
computability logic.
Journal
of Jilin University 47 (2009), pp. 1230-1236.
- L.Beklemishev,
On GLP-spaces.
Manusript, Steklov Institute of
Mathematics, 2009.
- I. Shapirovsky,
"PSPACE-decidability
of Japaridze's polymodal
logic".
Advances in Modal Logic 7 (2008), pp.
289-304.
- L.Beklemishev,
A
simplified proof of arithmetical completeness theorem for provability
logic GLP.
Proceedings of the Steklov Institute of Mathematics 274 (2011), pp.
25-33.
- N.Vereshchagin,
"Japaridze's
computability logic and intuitionistic propositional calculus".
Moscow State University preprint (Russian), 2006.
- G.Wang and W.Xu,
"Theorems
in the logic of tasks".
Fuzzy Systems
and Mathematics 20(2006),
No.6, pp. 15-20.
- H.Zhang and S.Li,
"The
description logic of tasks: from theory to practice".
Chinese Journal of Computers
29(2006), No.3, pp. 488-494.
- L.D. Beklemishev,
J.J. Joosten and M. Vervoort,
"A finitary treatment of the closed fragment of Japaridze's provability logic".
Journal of Logic and
Computation 15 (2005), No 4, pp. 447-463.
- G.Wang and W.Xu,
"From
the logic of facts to the logic of tasks".
Fuzzy Systems
and Mathematics 18(2004),
No.1, pp. 1-8.
- G. Boolos,
"The analytical completeness of Japaridze's polymodal logics".
Annals
of Pure and Applied Logic 61 (1993), pp. 95-111.
- K.
Ignatiev,
"The closed
fragment of Japaridze's polymodal
logic and the logic of Sigma-1 conservativity".
ITLI Prepublication Series for
Mathematical Logic and Foundations, X-92-02, University of Amsterdam, 1992.
- K. Ignatiev,
"Japaridze's polymodal logic:
arithmetical completeness, fixed point property, Craig's property".
ITLI Prepublication Series for
Mathematical Logic and Foundations, X-90-13, University of Amsterdam, 1990.
Technical Reports and
Unpublished Papers
- On the system CL12 of computability logic. arXiv:203.0103. 2012. 46 pages.
- The taming of recurrences in computability logic
through cirquent calculus, Part II. arXiv:1106.3705. 2011. 36 pages.
- The taming of recurrences in computability logic
through cirquent calculus, Part I. arXiv:1105.3853. 2011. 31
pages.
- A new face of the branching recurrence of computability
logic. arXiv:1102.1054. 2011. 6 pages.
- Introduction to clarithmetic
III. arXiv:1008.0770.
10 pages.
- Introduction to clarithmetic
II. arXiv:1004.3236. 2010. 28 pages.
- Introduction to clarithmetic
I. arXiv:1003.4719. 2010. 52 pages.
- A logical basis for constructive systems. arXiv:1003.0425. 2010. 30 pages.
- Separating the basic logics of the basic recurrences. arXiv:1007.1324.
2010. 18 pages.
- From formulas to cirquents in
computability logic. arXiv:0906.2154. 2009. 42 pages.
- Toggling operators in computability logic. arXiv:0904.3469. 2009. 43 pages.
- Ptarithmetic. arXiv:0902.2969. 2009. 103 pages.
- Towards applied theories based on computability logic. arXiv:0805.3521. 2008. 30 pages.
- Sequential operators in computability logic. arXiv:0712.1345, 2007. 40 pages.
- Cirquent calculus deepened. arXiv:0709.1308, 2007. 40 pages
- Many concepts and two logics of algorithmic reduction. arXiv:0706.0103,
2007. 15 pages.
- The intuitionistic fragment of computability logic at
the propositional level. arXiv:cs.LO/0602011,
2006. 59 pages.
- The logic of interactive Turing reduction. arXiv:cs.LO/0512100, 2005. 38 pages.
- In the beginning was game semantics. arXiv:cs.LO/0507045, 2005. 76 pages.
- Introduction to cirquent
calculus and abstract resource semantics. arXiv:math.LO/0506553, 2005. 50 pages.
- Intuitionistic computability logic. arXiv:cs.LO/0411008, 2004. 25 pages.
- From truth to computability II. arXiv:cs.LO/0501031, 2005. 34 pages.
- From truth to computability I. arXiv:cs.LO/0407054, 2004. 64 pages.
- Computability logic: a formal theory of interaction. arXiv:cs.LO/0404024, 2004. 26 pages.
- Propositional computability logic II. arXiv:cs.LO/0406037, 2004. 25 pages.
- Propositional computability logic I. arXiv:cs.LO/0404023, 2004. 22 pages.
- A formalism for resource-oriented
planning.
IRCS
Technical Reports 98-01 (1998), 38 pages.
- A decidable predicate logic of knowledge. IRCS Technical
Reports 96-06 (1996), 20 pages.
- (With D.DeJongh) The
logic of provability. ILLC
Prepublication Series for Mathematical Logic and Foundations
ML-1997-01.
- Effective truth. In: ILLC
Prepublication Series for Mathematical Logic and Foundations ML-93-15
(1993), 25 pages.
- The logic of tolerance. ILLC
Prepublication Series for Mathematical Logic and Foundations,
X-1991-08.
- Determinism and freedom of will. This philosophical
paper, written in Georgian, brought me the highest annual prize for
student research in Georgia called "Medal from the Academy of
Sciences of Georgian SSR" in 1982. I have never tried to
publish the manuscript, although I regard it as the most important of my
works. I am thinking of getting back to that exciting field in the
(perhaps not very near) future and writing a book.