Are you interested in using new ICT technology to boost your research?

Want to learn how to use high performance computing to speed up your calculations? Can you imagine the possibilities of scientific visualisation, and would you like to explore the power of big data analysis?

Discover new possibilities, experience the practical impact and do more with your data at the SURF Research Bootcamp.

The objective of our study was to find suitable classical equivalents of intuitionistic implication. Since the formula “p implies q” has infinitely many classical equivalents in the full fragment of intuitionistic propositional logic, we restricted ourselves first of all to finite fragments. In order to find the most suitable candidates we examined important features of the candidates in these fragments, such as reflexivity and transitivity. Additionally we examined if the formulas are weaker or stronger than intuitionistic implication and whether they are exact.

This is an invitation to reflect on the successes and failures of collective rationality, particularly as embodied in modern mechanisms for mass information-aggregation-and-exchange (media, markets, voting, social networks, crowdsourcing). Will 'truth' (the real truth) survive the ''information age"?

In this talk I will present an overview of some recent results involving applications of duality and category theory in automata and language theory.

One such strand of research involves a generic approach to  automata minimization. We depart from the standard coalgebraic approach and model automata as functors from a category specifying the input of the machine to another category which captures the structure of it's output. We identify sufficient conditions on the output category which ensure the existence of minimal automata. This allows us to cover awide range of examples by systematically applying the same category-theoretic principles in various instances.

A second research axis heavily uses duality theory to extend algebraic methods from the theory of regular languages to the non-regular setting. There are a plethora of results relating algebraic and logical characterizations of classes of regular languages. We aim to develop the tools that allow us to obtain such correspondences forclasses of non-regular languages. I will explain in detail how thesyntactic monoid of a language can be seen as the dual of the Booleanalgebra spanned by the quotients of that language. This paves the way for defining a suitable notion of recognisers for non-regular languages and to extend in this setting standard constructions from monoids that are the algebraic counterpart of logical quantifiers.

 (joint with Davide Grossi)

Coalition formation games model situations in which agents cooperate in teams, such as stable-roommate problems and project allocation problems, based on individual preferences of the agents. Questions of interests are related to stable and fair outcomes as well as representations of these games.

In this talk, firstly, an overview of hedonic games is given. These
can model agents' preferences over coalitions (i.e. sets of agents),
where the happiness of agents with a coalition structure only depends on their own coalition. Within the recent twenty years, various representations and stability notions, such as Nash stability, havebeen studied. Trade-offs exist between compact encodings and expressivity as well as the computational complexity of stability problems.

Secondly, a model of hedonic games with ordinal preferences and
thresholds is presented. Here, it is assumed that agents only know
a subset of their co-agents whom they partition into the sets of
friends and enemies. The remaining agents are considered as
neutral. At the same time they specify a weak order over the former
two sets. This relation is extended to a set of possible
preferences over coalitions such that it is reasonable to define
the notions of possible and necessary stability. While this model
can express preferences more generally than related models, the
complexity of various stability problems does not increase. Nevertheless many of these problems remain NP-hard or
even hard for the second level of the polynomial hierarchy.

In the literature natural restrictions are known that allow a decision
of some stability problems. Nevertheless, in order to evaluate
the stability of, e.g., a distribution into working groups, the
whole game has to be taken into consideration. In particular, in
large institutions or social networks, it would be desirable to
deduce global information from local samples.  Finally, in this
talk an initial result to tackle this problem with property
testing in the context of hedonic games is introduced.

In connection with Hugo Nobrega's PhD defense (Tuesday, April 24, at noon at the Agnietenkapel), we are having a small workshop with talks by some of the members of his thesis committee on April 24. Everyone is cordially invited to join!

The program is currently planned as follows:
15:30 - 16:15 Vasco Brattka, TBA
16:15 - 17:00 Jacques Duparc, TBA
17:00 - 17:45 Jouko Väänänen, "An extension of a theorem of Zermelo”
17:45 - 18:30 Arno Pauly, TBA

Peter Hawke discusses: 'ModalObjectivity' by Justin Clarke-Doane.

We prove an open mapping theorem for the topological spaces dual to finitely presented Heyting algebras. This yields in particular a short, self-contained semantic proof of the uniform interpolation theorem for intuitionistic propositional logic, first proved by Pitts in 1992. Our proof is based on the methods of Ghilardi & Zawadowski. However, our proof does not require sheaves nor games, only basic duality theory for Heyting algebras.

This talk will give a short introduction into computational social choice, an interdisciplinary field that lies at the interface between social choice theory and computer science. Afterwards the focus is on two different problems of collective decision making. The study of such problems is extremely important, since there are many situation where a collective decision based on individual preferences has to be made. The first part of this talk deals with the modeling of online participation processes and their properties. They will be formalized by abstract argumentation frameworks, where incompleteness is added to the initial model. This extension is more suitable to capture the dynamics of such processes. In this context the verification problem is particularly important, thus its computational complexity will be analyzed for different variants. The second part of the talk focuses on the algorithmic and axiomatic study of committee elections. Committee election rules for different forms of votes that try to minimize the voters’ dissatisfaction will be introduced. Afterwards its axiomatic and algorithmic properties are explored.