Spring 2012

Seminar in Computational Logic

Tuesday, 2:00pm - 4:00pm, room 3209 (Graduate Center)

February 14 meeting
Speaker: Antonis Achilleos (Graduate Center)
Title: The complexity of multi-agent explicit knowledge II
Abstract:

The purpose of the talk is to first give some background on the study of the complexity of justification logic and then proceed to present a family of multi-agent justification logics with interactions. We will then analyse the complexity of some of the simpler cases of this family that are closely connected to the single-agent cases.



February 7 meeting
Speaker: Antonis Achilleos (Graduate Center)
Title: The complexity of multi-agent explicit knowledge
Abstract:

The purpose of the talk is to first give some background on the study of the complexity of justification logic and then proceed to present a family of multi-agent justification logics with interactions. We will then analyse the complexity of some of the simpler cases of this family that are closely connected to the single-agent cases.


January 31 meeting
Speaker: Juoko Vaananen (Helsinki - IAS Princeton)
Title: The logic of dependence and independence
Abstract:

In my talk I isolate a concept of dependence (``Dependence Logic", Cambridge University Press, 2007) as well as a concept of independence and argue that these concepts, ubiquitous in science and humanities, but also in logic and computer science, can be taken as new atomic formulas in first order logic and be axiomatized like their cousin identity is axiomatized by the identity axioms. I will go on to show that while the resulting extension of first order logic is non-axiomatizable, there are canonical natural deduction rules which completely axiomatize first order consequences of sentences in this logic. On finite models the resulting logic gives a new analysis of NP. I will give a review of recent results on the expressive power of dependence and independence logics, as well as some applications.