<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Buss, Samuel R.</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Lower complexity bounds in justification logic</style></title><secondary-title><style face="normal" font="default" size="100%">Annals of Pure and Applied Logic</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">$\Pi^p_2$-completeness</style></keyword><keyword><style  face="normal" font="default" size="100%">computational complexity</style></keyword><keyword><style  face="normal" font="default" size="100%">Derivability problem</style></keyword><keyword><style  face="normal" font="default" size="100%">justification logic</style></keyword><keyword><style  face="normal" font="default" size="100%">Logic of Proofs</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2012</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.math.ucsd.edu/~sbuss/ResearchWeb/rlp_lower/APAL09_final.pdf</style></url></web-urls></urls><number><style face="normal" font="default" size="100%">7</style></number><volume><style face="normal" font="default" size="100%">163</style></volume><pages><style face="normal" font="default" size="100%">888–905</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">Justification Logic studies epistemic and provability phenomena by introducing justifications/proofs into the language in the form of justification terms. Pure justification logics serve as counterparts of traditional modal epistemic logics, and hybrid logics combine epistemic modalities with justification terms. The computational complexity of pure justification logics is typically lower than that of the corresponding modal logics. Moreover, the so-called reflected fragments, which still contain complete information about the respective justification logics, are known to be in NP for a wide range of justification logics, pure and hybrid alike. This paper shows that, under reasonable additional restrictions, these reflected fragments are NP-complete, thereby proving a matching lower bound. The proof method is then extended to provide a uniform proof that the corresponding full pure justification logics are $\Pi^p_2$-hard, reproving and generalizing an earlier result by Milnikel.</style></abstract><notes><style face="normal" font="default" size="100%">Published online November 2011</style></notes></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Remo Goetschi</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Realization for Justification Logics via Nested Sequents: Modularity through Embedding</style></title><secondary-title><style face="normal" font="default" size="100%">Annals of Pure and Applied Logic</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2012</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2012/gk12.pdf</style></url></web-urls></urls><language><style face="normal" font="default" size="100%">eng</style></language></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Samuel Bucheli</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author><author><style face="normal" font="default" size="100%">Thomas Studer</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Valentin Goranko</style></author><author><style face="normal" font="default" size="100%">Wojtek Jamroga</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Justifications for Common Knowledge</style></title><secondary-title><style face="normal" font="default" size="100%">Journal of Applied Non-classical Logics</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2011</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2011/bks11a.pdf</style></url></web-urls></urls><volume><style face="normal" font="default" size="100%">21</style></volume><pages><style face="normal" font="default" size="100%">35-60</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><issue><style face="normal" font="default" size="100%">1</style></issue><notes><style face="normal" font="default" size="100%">To appear, 2011</style></notes><section><style face="normal" font="default" size="100%">35</style></section></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Samuel Bucheli</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author><author><style face="normal" font="default" size="100%">Thomas Studer</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Beklemishev, Lev D.</style></author><author><style face="normal" font="default" size="100%">de Queiroz, Ruy</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Partial Realization in Dynamic Justification Logic</style></title><secondary-title><style face="normal" font="default" size="100%">Logic, Language, Information and Computation, 18th International Workshop, WoLLIC 2011, Philadelphia, PA, USA, May 18-20, 2011, Proceedings</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Lecture Notes in Artificial Intelligence</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2011</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2011/bks11b.pdf</style></url></web-urls></urls><volume><style face="normal" font="default" size="100%">6642</style></volume><pages><style face="normal" font="default" size="100%">35-51</style></pages><language><style face="normal" font="default" size="100%">eng</style></language></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Samuel Bucheli</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author><author><style face="normal" font="default" size="100%">Thomas Studer</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Explicit Evidence Systems with Common Knowledge</style></title></titles><dates><year><style  face="normal" font="default" size="100%">2010</style></year><pub-dates><date><style  face="normal" font="default" size="100%">may</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://arxiv.org/abs/1005.0484</style></url></web-urls></urls><number><style face="normal" font="default" size="100%">1005.0484</style></number><publisher><style face="normal" font="default" size="100%">arXiv.org</style></publisher><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">Justification logics are epistemic logics that explicitly include justifications for the agents' knowledge. We develop a multi-agent justification logic with evidence terms for individual agents as well as for common knowledge. We define a Kripke-style semantics that is similar to Fitting's semantics for the Logic of Proofs $\mathsf{LP}$. We show the soundness, completeness, and finite model property of our multi-agent justification logic with respect to this Kripke-style semantics. We demonstrate that our logic is a conservative extension of Yavorskaya's minimal bimodal explicit evidence logic, which is a two-agent version of $\mathsf{LP}$. We discuss the relationship of our logic to the multi-agent modal logic $\mathsf{S4}$ with common knowledge. Finally, we give a brief analysis of the coordinated attack problem in the newly developed language of our logic.</style></abstract><work-type><style face="normal" font="default" size="100%">E-print</style></work-type></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>17</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Self-Referential Justifications in Epistemic Logic</style></title><secondary-title><style face="normal" font="default" size="100%">Theory of Computing Systems</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">epistemic modal logic</style></keyword><keyword><style  face="normal" font="default" size="100%">justification logic</style></keyword><keyword><style  face="normal" font="default" size="100%">Logic of Proofs</style></keyword><keyword><style  face="normal" font="default" size="100%">self-referentiality</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2010</style></year><pub-dates><date><style  face="normal" font="default" size="100%">may</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2010/kuz10.pdf</style></url></web-urls></urls><number><style face="normal" font="default" size="100%">4</style></number><volume><style face="normal" font="default" size="100%">46</style></volume><pages><style face="normal" font="default" size="100%">636–661</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">This paper is devoted to the study of self-referential proofs and/or justifications, i.e., valid proofs that prove statements about these same proofs. The goal is to investigate whether such self-referential justifications are present in the reasoning described by standard modal epistemic logics such as~$\mathsf{S4}$. We argue that the modal language by itself is too coarse to capture this concept of self-referentiality and that the language of justification logic can serve as an adequate refinement. We consider well-known modal logics of knowledge/belief and show, using explicit justifications, that~$\mathsf{S4}$, $\mathsf{D4}$, $\mathsf{K4}$, and~$\mathsf{T}$ with their respective justification counterparts~$\mathsf{LP}$, $\mathsf{JD4}$, $\mathsf{J4}$, and~$\mathsf{JT}$ describe knowledge that is self-referential in some strong sense. We also demonstrate that self-referentiality can be avoided for~$\mathsf{K}$ and~$\mathsf{D}$.

In order to prove the former result, we develop a machinery of minimal evidence functions used to effectively build models for justification logics. We observe that the calculus used to construct the minimal functions axiomatizes the reflected fragments of justification logics. We also discuss difficulties that result from an introduction of negative introspection.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Samuel Bucheli</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author><author><style face="normal" font="default" size="100%">Thomas Studer</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Thomas Bolander</style></author><author><style face="normal" font="default" size="100%">Torben Braüner</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Two Ways to Common Knowledge</style></title><secondary-title><style face="normal" font="default" size="100%">Proceedings of the 6th Workshop on {M}ethods for {Modalities} ({M4M–6 2009}), {C}openhagen, {D}enmark, 12–14 {N}ovember 2009</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Electronic Notes in Theoretical Computer Science</style></tertiary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">common knowledge</style></keyword><keyword><style  face="normal" font="default" size="100%">justification logics</style></keyword><keyword><style  face="normal" font="default" size="100%">proof theory</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2010</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2010/bks10a.pdf</style></url></web-urls></urls><number><style face="normal" font="default" size="100%">262</style></number><publisher><style face="normal" font="default" size="100%">Elsevier</style></publisher><pages><style face="normal" font="default" size="100%">83–98</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">It is not clear what a system for evidence-based common knowledge should look like if common knowledge is treated as a greatest fixed point. This paper is a preliminary step towards such a system. We argue that the standard induction rule is not well suited to axiomatize evidence-based common knowledge. As an alternative, we study two different deductive systems for the logic of common knowledge. The first system makes use of an induction axiom whereas the second one is based on co-inductive proof theory. We show the soundness and completeness for both systems.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Samuel Bucheli</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author><author><style face="normal" font="default" size="100%">Renne, Bryan</style></author><author><style face="normal" font="default" size="100%">Sack, Joshua</style></author><author><style face="normal" font="default" size="100%">Thomas Studer</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Arrazola, Xabier</style></author><author><style face="normal" font="default" size="100%">Ponte, Mar\'ıa</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Justified Belief Change</style></title><secondary-title><style face="normal" font="default" size="100%">Proceedings of the {S}econd {ILCLI} {I}nternational {W}orkshop on {L}ogic and {P}hilosphy of {K}nowledge, {C}ommunication and {A}ction ({L}og{KCA}-10)</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2010</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2010/bkrss10.pdf</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">University of the Basque Country Press</style></publisher><pages><style face="normal" font="default" size="100%">135–155</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">Justification Logic is a framework for reasoning about evidence and justification. Public Announcement Logic is a framework for reasoning about belief changes caused by public announcements. This paper develops JPAL, a dynamic justification logic of public announcements that corresponds to the modal theory of public announcements due to Gerbrandy and Groeneveld. JPAL allows us to reason about evidence brought about by and changed by Gerbrandy–Groeneveld-style public announcements.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Kai Brünnler</style></author><author><style face="normal" font="default" size="100%">Remo Goetschi</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Lev Beklemishev</style></author><author><style face="normal" font="default" size="100%">Valentin Goranko</style></author><author><style face="normal" font="default" size="100%">Valentin Shehtman</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">A Syntactic Realization Theorem for Justification Logics</style></title><secondary-title><style face="normal" font="default" size="100%">Advances in Modal Logic, Volume 8</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">justification logic</style></keyword><keyword><style  face="normal" font="default" size="100%">modal logic</style></keyword><keyword><style  face="normal" font="default" size="100%">nested sequents</style></keyword><keyword><style  face="normal" font="default" size="100%">positive introspection</style></keyword><keyword><style  face="normal" font="default" size="100%">realization theorem</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2010</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2010/bgk10.pdf</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">College Publications</style></publisher><pages><style face="normal" font="default" size="100%">39–58</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">Justification logics are refinements of modal logics where modalities are replaced by justification terms. They are connected to modal logics via so-called realization theorems. We present a syntactic proof of a single realization theorem that uniformly connects all the normal modal logics formed from the axioms $\mathsf{d}$, $\mathsf{t}$, $\mathsf{b}$, $\mathsf{4}$, and $\mathsf{5}$ with their justification counterparts. The proof employs cut-free nested sequent systems together with Fitting's realization merging technique. We further strengthen the realization theorem for $\mathsf{KB5}$ and $\mathsf{S5}$ by showing that the positive introspection operator is superfluous.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Artemov, Sergei</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Aviad Heifetz</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Logical Omniscience as a Computational Complexity Problem</style></title><secondary-title><style face="normal" font="default" size="100%">Theoretical {A}spects of {R}ationality and {K}nowledge, Proceedings of the Twelfth Conference ({TARK 2009})</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2009</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2009/ak09.pdf</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">ACM</style></publisher><pub-location><style face="normal" font="default" size="100%">Stanford University, California</style></pub-location><pages><style face="normal" font="default" size="100%">14–23</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">The logical omniscience feature assumes that an epistemic agent knows all logical consequences of her assumptions. This paper offers a general theoretical framework that views logical omniscience as a computational complexity problem. We suggest the following approach: we assume that the knowledge of an agent is represented by an epistemic logical system~$E$; we call such an agent \emph{not logically omniscient} if for any valid knowledge assertion~$\mathcal{A}$ of type \emph{$F$~is known}, a proof of~$F$ in~$E$ can be found in polynomial time in the size of~$\mathcal{A}$. We show that agents represented by major modal logics of knowledge and belief are logically omniscient, whereas agents represented by justification logic systems are not logically omniscient with respect to \emph{$t$~is a justification for~$F$}.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Buss, Samuel R.</style></author><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Artemov, Sergei</style></author><author><style face="normal" font="default" size="100%">Nerode, Anil</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">The NP-completeness of reflected fragments of justification logics</style></title><secondary-title><style face="normal" font="default" size="100%">Proceedings of {S}ymposium on {L}ogical {F}oundations of {C}omputer {S}cience ({LFCS}'09)</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Lecture Notes in Computer Science</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2009</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2009/bk09.pdf</style></url></web-urls></urls><volume><style face="normal" font="default" size="100%">5407</style></volume><pages><style face="normal" font="default" size="100%">122-136</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">Justification Logic studies epistemic and provability phenomena by introducing justifications/proofs into the language in the form of justification terms. Pure justification logics serve as counterparts of traditional modal epistemic logics, and hybrid logics combine epistemic modalities with justification terms. The computational complexity of pure justification logics is typically lower than that of the corresponding modal logics. Moreover, the so-called reflected fragments, which still contain complete information about the respective justification logics, are known to be in~NP for a wide range of justification logics, pure and hybrid alike. This paper shows that, under reasonable additional restrictions, these reflected fragments are NP-complete, thereby proving a matching lower bound.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Kuznets, Roman</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Costas Drossos</style></author><author><style face="normal" font="default" size="100%">Pavlos Peppas</style></author><author><style face="normal" font="default" size="100%">Constantine Tsinakis</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">A Note on the Use of Sum in the Logic of Proofs</style></title><secondary-title><style face="normal" font="default" size="100%">Proceedings of the 7th {P}anhellenic {L}ogic {S}ymposium</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2009</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.iam.unibe.ch/ltgpub/2009/kuz09b.pdf</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Patras University Press</style></publisher><pub-location><style face="normal" font="default" size="100%">Patras University, Greece</style></pub-location><pages><style face="normal" font="default" size="100%">99–103</style></pages><language><style face="normal" font="default" size="100%">eng</style></language></record></records></xml>
