Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Roman Kuznets

City University of New York

Justification, Complexity, Self-Referentiality

Abstract:

Justification Logic is a relatively new field that studies provability, knowledge, and belief via proofs, or justifications, explicitly present in the language. Many justification logics have been developed that closely resemble modal epistemic logics of knowledge and belief with one important difference: instead of modality box with existential epistemic reading 'there exists a proof of $F$,' justification logics operate with constructs $t :F$, where a justification term $t$ represents a blueprint of a Hilbert-style proof of $F$. The machinery of explicit justifications can be used to analyze well-known epistemic paradoxes such as Gettier's examples, to study self-referential properties of modal logics, and to avoid Logical Omniscience. This talk will focus on quantitative analysis of justification logics. We will give an overview of what is known about their decidability and complexity of the decision procedure. We will also analyze a realization procedure that provides a bridge from a modal epistemic logic to its justification counterpart. We will discuss the complexity of one such realization procedure as well as provide its qualitative analysis that leads to interesting corollaries about self-referentiality of modal logics.

Host: Sam Buss

April 22, 2008

4:00 PM

AP&M 7321

****************************