'LogICCC meets China' Day October 7

Overview

There will be a special meeting the day before the workshop (October 7, 2009) where members of LogiCCC will present and discuss their research projects with Chinese colleagues.

The meeting is sponsored by the European Science Foundation and the Southwest University, Chongqing

Participants

Johan van Benthem (Amsterdam)
Dietmar Berwanger (Aachen)
Ulle Endriss (Amsterdam)
Jouko Väänänen (Amsterdam)
Dag Westerståhl (Gothenburg)

Schedule

(Preliminary Program)
9:00 - 9:30: Opening and introduction
Johan van Benthem (University of Amsterdam & Stanford)
9:30 - 10:15: LogiCCC Invited Speaker
Ulle Endriss (Amsterdam)
Logic and social choice theory

Abstract: Social choice theory, a scientific discipline developed largely in mathematical economics and political science, addresses questions regarding the design and analysis of methods for collective decision making. Examples for such methods include voting procedures and protocols for fairly dividing a set of goods amongst the members of a group. The emerging field of computational social choice studies these questions from a computational perspective, making use of a variety of tools and techniques, including logic. In this talk I will first give a brief introduction to computational social choice and then highlight a number of recent research directions that make use of logic in different ways: the compact representation of preferences in terms of weighted formulas, the aggregation of judgments regarding logically interconnected propositions, and the formal specification of social choice mechanisms.
(hide abstracts)

10:15 - 11:00: LogiCCC Invited Speaker
Jouko Väänänen (Amsterdam)
Dependence logic
11:00 - 11:30: Break
11:30 - 12:30: Poster Session (hide abstracts)
Jianying Cui, Meiyun Guo and Xiaojia Tang (Chongqing)
Characterizations of iterated admissibility based on PEGL
Abstract: Iterated dominance is perhaps the most basic principle in game theory. The epistemic foundation of this principle is based on the assumption that all players are rational. The main contribution of this paper is to characterize the algorithm of iterated admissibility in Probabilistic Epistemic Game Logic (PEGL). Firstly, on the basis of Probabilistic Epistemic Logic we set up a logic PEGL. Secondly, by redefining a concept of rationality, we show that common knowledge of the rationality characterizes the algorithm of Iterated Admissibility, that is, we provide an epistemic foundation for the solutions or equilibria which are found by the algorithm of Iterated Admissibility. Next, inspired by van Benthem, we provide a different characterization of iterated admissibility using public announcement of the rationality in dynamic logic. The results we obtain can be seen as giving a dynamic epistemic foundation for the algorithm of Iterated Admissibility.
(hide abstracts)

Antti Kuusisto (Tampere)
Monadic Sigma-1-1 and modal logic with quantified binary relations
Abstract: We consider a range of modal logics with existential second-order prenex quantification of binary (and unary) relations. We show that these logics can be translated to Existential Monadic Second-Order Logic, so in fact we identify fragments of Sigma-1-1 that translate to Existential Monadic Second-Order Logic. These results give rise to a method for establishing decidability results related to satisfiability questions for a variety of extensions of multimodal logic. We briefly discuss applications of modal logic where such extensions have proved successful.
(hide abstracts)

Fenrong Liu (Beijing)
Modelling preference, knowledge, and beliefs in games
Abstract: The notion of preference occurs together with knowledge and beliefs in games or real scenarios in which agents need to make decisions. Preferences of rational agents are based on their knowledge and belief, moreover, agents often have epistemic/doxastic introspection on their preferences. In particular, when acting under uncertainties in games, one agent must have beliefs about her opponent's preference. Notions of preference, knowledge and beliefs are delicately entangled. In this talk we will explore various ways of such an entanglement, propose a series of corresponding logic systems, and show how the valid logical principles characterize these phenomena that we encounter frequently in games.
(hide abstracts)

Yong-qiang Lou (Qingtao)
A kind of tableau systems of idealized information flow logic
Abstract: Based on Jon Barwise’s theory of information flow and Graham Priest’s method to construct logical systems, we have attempted to construct a kind of tableau systems for the idealized information flow in Barwise’s sense. Syntactically, the information flow implication is introduced, which is explained in terms of the ternary relation between situations and channels. In order to avoid technical complexity, situations and channels are treated in the information frames as being the same type of information entities. Priest’s method to prove the soundness and completeness of his tableau systems also paves the way for the proof of the soundness and completeness of our tableau systems of the idealized information flow logic.
(hide abstracts)

Allen Mann (Tampere)
IF algebras
Abstract: Independence-friendly logic (IF logic) is a conservative extension of first-order logic with the same expressive power as existential second-order logic. Cylindric algebra is the algebra of first-order logic in the same way that Boolean algebra is the algebra of propositional logic. I define independence-friendly cylindric set algebras (IF algebras) in an attempt to algebraize IF logic.
(hide abstracts)

Daniele Porello (Amsterdam)
Linear logic for bidding languages
Abstract: See pdf file.
(hide abstracts)

Fangfang Tang (Beijing)
Generalized Sheffer-stroke based analytical modal axiomatic systems
Abstract: Our main objective is to propose analytic axiomatic systems for some normal modal logics, in which the proof of theorem is easy. An axiomatic system is called analytic, if the premises and consequences of its inferential rules share propositional variables. Our results in modal logic follow the original work of Anderson et al, who propose analytic axiomatic systems for classical logic. We first define an n-ary operator and give a new notation of modal formulas, which is convenient to express the axioms of such systems and saves the connectives and parentheses. And so we name it generalized Sheffer stroke. We give the strong completeness theorems and interpolation theorems for such systems. Besides, we propose a new definition of derivation in terms of them. Although they have no Modus Ponens, the analytic axiomatic systems have common conditions on the deducibility relation, such as reflexivity, monotonicity, and cut.
(hide abstracts)

Michael Ummels (Aachen)
The complexity of Nash equilibria in stochastic games
Abstract: We analyse the computational complexity of finding Nash equilibria in simple stochastic multiplayer games (SSMGs). We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given an SSMG G, does there exist a pure-strategy Nash equilibrium of G where player 0 wins with probability 1? Moreover, this problem remains undecidable if it is restricted to strategies with (unbounded) finite memory. However, if mixed strategies are allowed, decidability remains an open problem. One way to obtain a provably decidable variant of the problem is restricting the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSPACE, respectively. These upper bounds still hold when one considers more complex objectives such as Büchi, parity or Muller objectives.
(hide abstracts)

Fan Yang (Helsinki)
Intuitionistic universal models of NNIL-formulas
Abstract: See pdf file.
(hide abstracts)

12:30 - 14:00: Lunch
14:00 - 14:45: LogiCCC Invited Speaker
Dietmar Berwanger (Paris, Aachen)
On the fragility of perfect information
14:45 - 15:30: LogiCCC Invited Speaker
Dag Westerståhl (Gothenburg)
Logical constants and logical consequence
Abstract: Virtually every definition of a logical system or a notion of logical consequence, whether model-theoretic or proof-theoretic, presupposes a selection of logical constants, leaving us with the familiar problem of how this selection is made. What is it about a meaningful expression that makes it earn the label ‘logical’? Why are, in English, words like ‘Mary’, ‘apple’, or ‘green’ never considered logical whereas ‘every’ and ‘not’ are? After a brief survey of known approaches to this question I sketch some recent work within the LogICCC project LINT (Logic for Interaction), suggesting that it may be fruitful to change perspective and take consequence relations as primitive instead, and extract the constants from them.
(hide abstracts)
15:30 - 16:00: Break
16:00 - 17:15: Young Researcher's Forum: 12 minute presentations (hide abstracts)
Jesse Alama (Lisbon)
Dialogues and arguments in mathematical proofs
Abstract: Dialogue games are one of the earliest examples of games in logic (they were introduced by Lorenzen in the 1950s). Although the subject has attracted a number of scholars (Lorenz, Rahman, Tulenheimo, van Benthem) and enjoys considerable intuitive appeal, the field seems to have been stagnant for several years. Thankfully, these days dialogues are enjoying a small-scale revival. My work as a port-doctoral student within the LogICCC framework, under the supervision of Reinhard Kahle and in cooperation with two other LogiCCC groups based in Amsterdam and Tübingen, is devoted to dialogues and argumentation, specifically mathematical argumentation. The project thus involves technical problems such as developing a structure theory for Lorenzen dialogue games and extending such games to include other kinds of dialogical interactions (for example, mutual observation). The project also aims to take on philosophical problems in epistemology, philosophy of mathematics, and argumentation theory by using dialogues as a common frame of reference for (i) characterizing mathematical argumentation, (ii) investigating computer-checked formal proofs, and (iii) exploring the fascinating topic of zero-knowledge proofs in cryptography.
(hide abstracts)

Jiahong Guo (Beijing)
Attempting to combine belief and higher-order knowledge into Pacuit & Parikh’s logic of communication graphs
Abstract: In 2005 Pacuit and Parikh studied a kind of logic for communication graphs based on a multi-agent language with a communication modality. They assumed that agents are connected by a communication graph. There an edge from agent i to agent j means that agent i can directly receive information from agent j. Then if j knows something that ϕ, it is possible for i to learn ϕ through communication with j. I would like to introduce a classical belief modality into their multi-agent language in order to describe the process of communicating (update & revision may be included) belief and learning of higher-order knowledge and belief. Some special issues such as communication with Moorean type information will be re-considered with the help of the above communication graph models.
(hide abstracts)

Pietro Galliani (Amsterdam)
Sensible semantics on infinite structures
Abstract: : In [Cameron and Hodges, Some combinatorics of imperfect infrmation, JSL, 66, 2001] it is proved that no compositional semantics which assigns sets of tuples of elements to formulas which one free variable may be correct for a logic of imperfect information such as IF-Logic or Dependence Logic. Hodges and Cameron observe that the argument used is not applicable if we only consider infinite models, but nonetheless conjecture that no such "sensible" semantics exists. In this presentation, I will introduce a formal, natural definition of "sensible semantics" which makes the above statement true.
(hide abstracts)

Hu Liu (Guangzhou)
An evaluation of degrees of uncertainty in nonmonotonic reasoning
Abstract: In a nonmonotonic logic, a consequence A from a knowledge base may be retracted as the knowledge base is extended. We may regain A by further extending the knowledge base, and may lose it again along an extending path. The situation of A switches over a path. Each switch is called a mind change. Take default logic for example, if a default theory is finite, then there can only exist finitely many mind changes along any path before it converges, that is, there are no further switches no matter how you extend the knowledge base. In this case we say that the knowledge base is stable with respect to A, or there is no uncertainty of A. We evaluate the degree of uncertainty by the number of mind changes. This concept of uncertainty is inherent in a default theory. It does not rely on any outside relations. The idea is borrowed from algorithm learning theory, where the number of mind changes is considered as an evaluation of learning complexity.
(hide abstracts)

Umberto Grandi (Amsterdam)
Complexity of judgement aggregation
Abstract: See pdf file.
(hide abstracts)

Minghui Ma (Beijing)
Graded modal frame definability
Abstract: The general problem to be concerned with is the following: how far can some important logical properties or theorems within certain theories for basic modal logic be extended to richer modal languages? Let's consider the Goldblatt-Thomason theorem (1974) which transfers Birkoff’s theorem for universal algebra saying that a class of algebras is equationally definable iff it is a variety into the basic modal language. The model-theoretic version (proof) of it given by Johan van Benthem (1993) says that an elementary class of frames is definable in the basic modal language iff it is closed under taking disjoint unions, generated subframes, p-morphic images, and anti-closed under taking ultrafilter extensions. There are several ways to generalize it. What I am concerned with is frame definability in graded modal language. Two roads are taken to analyze it. One is to analyze frame first-order correspondence theory for graded modal logic. The graded modal Sahlqvist correspondence theorem holds. The other is a semantic one. Two important model-theoretic constructions, graded p-morphism and graded ultrafilter extension, are defined. The main theorem is to prove a weak Goldblatt-Thomason theorem, i.e., an elementary class of frames is graded modally definable by a set of closed graded modal formulas iff it is closed under taking disjoint unions, generated subframes and global graded bisimular images, and anti-closed under graded ultrafilter extensions.
(hide abstracts)

17:15 - 17:30: YRF General Discussion
Evening: Strategic meeting with open discussion about future research opportunities