Interpreting Knowledge into Belief in the Presence of Negative IntrospectionEvan Goris, Technical Report TR-2007005, CUNY Ph.D. Program in Computer Science, 2007 bibtex abstractAbstract:
This paper studies a particular interpretation of propositional modal
logic into propositional modal logic. Under an epistemic reading of the
modality this interpretation can be understood as taking knowledge to be
true belief. All normal modal logics of belief that under this definition
of knowledge give rise to S5 as the logic of knowledge are determined.
And all the normal modal logics of belief that give rise to S4w5 as the
logic of knowledge are determined. Among the latter KD45 shows up as
a maximal such logic.
@TechReport{cite-key,
title={Interpreting Knowledge into Belief in the Presence of Negative Introspection},
author={Evan Goris},
year={2007},
number={TR-2007005},
institution={CUNY Ph.D.~Program in Computer Science}
}
Interpolation and the Interpretability Logic of PAEvan Goris, Notre Dame Journal of Formal Logic, 47(2):179–195, 2006 bibtex abstractAbstract:
In this paper we will be concerned with the interpretability logic of PA and in particular with the fact that this logic, which is denoted by ILM, does not have the interpolation property. An example for this fact seems to emerge from the fact that ILM cannot express Σ1-ness. This suggests a way to extend the expressive power of interpretability logic, namely, by an additional operator for Σ1-ness, which might give us a logic with the interpolation property. We will formulate this extension, give an axiomatization which is modally complete and arithmetically complete (although for proofs of these theorems we refer to an earlier paper), and investigate interpolation. We show that this logic still does not have the interpolation property.
@Article{cite-key,
title={Interpolation and the Interpretability Logic of {\textsf{PA}}},
author={Evan Goris},
journal={Notre Dame Journal of Formal Logic},
volume={47},
year={2006},
number={2},
pages={179--195}
}
Explicit Proofs in Formal Provability LogicEvan Goris, Technical Report TR-2006003, CUNY Ph.D. Program in Computer Science, 2006 bibtex abstractAbstract: In this paper we answer the question what implicit proof assertions in the provability logic GL can be realized by explicit proof terms. In particular we show that the fragment of GL which can be realized by generalized proof terms of GLA is exactly S4 intersected with GL and equals the fragment that can be realized by proof terms of LP. Additionally we show that the problem of determining which implicit provability assertions in a given modal formula can be made explicit is decidable. In the final sections of this paper we establish the disjunction property for GLA and give an axiomatization for S4 intersected with GL. @TechReport{cite-key,
title={Explicit Proofs in Formal Provability Logic},
author={Evan Goris},
year={2006},
number={TR-2006003},
institution={CUNY Ph.D.~Program in Computer Science}
}
Logic of Proofs for Bounded ArithmeticEvan Goris, In
Computer Science - Theory and Applications: First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12. 2006, volume 3967 of
Lecture Notes in Computer Science, pages 191–201, 2006
bibtex abstractAbstract: The logic of proofs is known to be complete for the semantics of proofs in Peano Arithmetic
PA. In this paper we present a refinement of this theorem, we will show that we can assure that all the operations on proofs can be realized by feasible, that is PTIME-computable, functions. In particular we will show that the logic of proofs is complete for the semantics of proofs in Buss's bounded arithmetic
S12. In view of recent applications of the Logic of Proofs in epistemology this result shows that explicit knowledge in the propositional framework can be made computationally feasible. @InProceedings{cite-key,
title={Logic of Proofs for Bounded Arithmetic},
author={Evan Goris},
volume={3967},
year={2006},
series={Lecture Notes in Computer Science},
publisher={Elsevier},
booktitle={Computer Science - Theory and Applications: First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12. 2006},
pages={191--201}
}
PDL for Ordered TreesLoredana Afanasiev, Patrick Blackburn, Ioanna Dimitriou, Bertrabd Gaiffe, Evan Goris, Maarten Marx, and Maarten de Rijke, Journal of Applied Non-Classical Logics, 15(2):115–135, 2005 bibtex abstractAbstract:
This paper is about a special version of PDL, proposed by Marcus Kracht, for rea-
soning about sibling ordered trees. It has four basic programs corresponding to the child,
parent, left- and right-sibling relations in such trees. The original motivation for this language
is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area
of semi-structured data, and, especially, in the field of query languages for XML (eXtensible
Markup Language) documents, we revisit the language. This renewed interest comes with a
special focus on complexity and expressivity aspects of the language, aspects that have so far
largely been ignored. We survey and derive complexity results, and spend most of the paper
on the most important open question concerning the language: what is its expressive power?
We approach this question from two angles: Which first-order properties can be expressed?
And which second-order properties? While we are still some way from definitive answers to
these questions, we discuss two first-order fragments of the PDL language for ordered trees,
and show how the language can be used to express some typical (second-order) problems, like
the boolean circuit and the frontier problem.
@Article{cite-key,
title={\textsf{PDL} for Ordered Trees},
author={Loredana Afanasiev, Patrick Blackburn, Ioanna Dimitriou, Bertrabd Gaiffe, Evan Goris, Maarten Marx, and Maarten de Rijke},
journal={Journal of Applied Non-Classical Logics},
volume={15},
year={2005},
number={2},
pages={115--135}
}
The Many Faces of InterpretabilityEvan Goris and Joost J. Joosten, Technical Report PP-2005-15, ILLC, 2005 bibtex abstract<<no abstract available>> @TechReport{cite-key,
title={The Many Faces of Interpretability},
author={Evan Goris and Joost J. Joosten},
year={2005},
number={PP-2005-15},
institution={ILLC}
}
Looping CaterpillarsEvan Goris and Maarten Marx, In
Twentieth Annual IEEE Symposium on Logic in Computer Science, pages 51–60, 2005
bibtex abstract<<no abstract available>> @InProceedings{cite-key,
title={Looping Caterpillars},
author={Evan Goris and Maarten Marx},
year={2005},
booktitle={Twentieth Annual IEEE Symposium on Logic in Computer Science},
pages={51--60}
}
Smart LabelsMarta Bilkova, Evan Goris, and Joost J. Joosten, In
Liber Amicorum for Dick de Jongh, 2004
bibtex abstract<<no abstract available>> @InCollection{cite-key,
title={Smart Labels},
author={Marta Bilkova, Evan Goris, and Joost J. Joosten},
year={2004},
publisher={Institute for Logic, Language and Computation},
booktitle={Liber Amicorum for Dick de Jongh}
}
Modal Matters in Interpretability LogicsEvan Goris and Joost J. Joosten, Technical Report LGPS-226, University of Utrecht Logic Group, 2004 bibtex abstract<<no abstract available>> @TechReport{cite-key,
title={Modal Matters in Interpretability Logics},
author={Evan Goris and Joost J. Joosten},
year={2004},
number={LGPS-226},
institution={University of Utrecht Logic Group}
}
Extending ILM with an Operator for Σ1-nessEvan Goris, Technical Report PP-2003-17, ILLC, 2003 bibtex abstract<<no abstract available>> @TechReport{cite-key,
title={Extending IL\textsf{M} with an Operator for $\Sigma_1$-ness},
author={Evan Goris},
year={2003},
number={PP-2003-17},
institution={ILLC}
}