Institute of Computer Science


News and Events

SNSF granted a new four year project to our research group


Explicit reasons

This project is concerned with reasons why one believes something, reasons why one knows something, and reasons why one ought to do something. We develop formal languages in which reasons can be represented explicitly and investigate the logical properties of explicit reasons. To achieve this, we rely on the framework of justification logic. In particular, we present non-normal deontic logics with justifications. Further, we develop a semiring framework for justifications, and we engineer a possible world semantics for justifications that supports additional structure like graded justifications or probability distributions on justifications.


Ioannis Kokkinis: The Dynamic Complexity of Acyclic Conjunctive Queries

Conjunctive queries (CQs) are a simple but important class of first-order definable queries. They correspond to SELCT-PROJECT-JOIN SQL queries, so they are part of almost every database query language. The importance of this class of queries is also demonstrated by the fact that the evaluation problem for CQs is a generalisation of several important problems in computer science, like the Graph Homomorphism Problem or the Boolean Satisfiability Problem. While the evaluation problem for CQs is in general NP-complete, there are interesting special cases of this problem that admit very fast algorithms (both in theory and in practise). For example the combined complexity (that means when both the CQ and the database are part of the input) of the evaluation problem for acyclic conjunctive queries (ACQs) is extremely low (it lies in the class LOGCFL, which means that it can be solved in polylogarithmic parallel time). The same holds for determining whether a CQ is acyclic. In this talk we study the combined complexity for the evaluation problem in acyclic conjunctive queries from a dynamic point of view. The goal of dynamic complexity is to determine the minimum resources needed for maintaining the answer to a problem when the input changes dynamically. An important dynamic complexity class is the class DynFO which contains all problems that can be maintained using first order formulas after single tuple insertions and deletions into/from the input. We show that the result of the evaluation of an ACQ can be maintained in DynFO after insertions and deletions of atoms into/from the query and also that it is very unlikely that the evaluation result of an ACQ can be maintained in DynFO after both changes in the database and the query. Finally we show that determining whether a query is acyclic can also be maintained in DynFO.

LTG Seminar, Thursday, April 11, at 9:30 in room A97 ExWi Building

Stepan Kuznetsov: Divide and Iterate

In this talk we briefly survey previously known and new results on the complexity, elements of proof theory, and algebraic semantics of action logic, that is, the (in)equational theory of residuated Kleene lattices, and its fragments. We emphasize the fact that adding division operations, i.e., moving from Kleene algebras to residuated ones, changes things dramatically. Namely, the systems become undecidable, and induction-based axiomatizations of iteration (Kleene star) become incomplete.

LTG Seminar, Thursday, April 11, at 9:30 in room A97 ExWi Building

Tomáš Nagy: Selfdistributive quasigroups

Selfdistributive quasigroups are interesting examples of non-associative algebraical structures. Even though the concept of selfdistributivity (e.g. the identity a*(b*c) = (a*b)*(a*c)) might sound abstract, it has interesting applications in low-dimensional topology and in many other areas of mathematics. After introducing the basic concepts, we will focus on non-affine seldistributive quasigroups, e.g. those that are not polynomially equivalent to some module. We will explain the reasons why it is not easy to classify them and we will introduce the first example of such a quasigroup that was introduced by Onoi in the year 1970. At the end, we will show a generalization of this construction that allows us to construct such quasigroups of size 2^k for all k > 5 (except for 7). We will also introduce the concept of central extensions that transforms the problem of finding non-affine selfdistributive quasigroups into solving system of linear equations over some abelian group.