The aim of this tutorial is to give an introduction into social choice theory with special emphasis on tools of general relevance developed in this area (as extensions of rankings of objects to sets and distance-based approaches) and recent extensions (e.g. judgment aggregation).

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)

The aim of this tutorial is to give an introduction into social choice theory with special emphasis on tools of general relevance developed in this area (as extensions of rankings of objects to sets and distance-based approaches) and recent extensions (e.g. judgment aggregation).

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)

The problem to assign papers to referees gained a considerable interest in the recent years, especially in the scope of conference management systems. These systems need to achieve a fair and balanced distribution of papers among referees, where the conditions of fairness and balance may be defined in several ways. We present two algorithms to distribute a possibly large number of papers among a smaller number of referees, each paper requiring k reports. The first one is an approximation algorithm, using an iteration of weighted maximum matching in bipartite graphs. The second one is an exact algorithm based on b-matching. The optimality criterion for the assignment is not based on a local view of each referee, but on a global performance of the whole k-assignment satisfying a fairness criterion. We introduce an objective function for the k-assignment problem ensuring a specific notion of fairness when it is maximized. We show how a few precisely defined fairness criteria can be achieved that way. This includes a particularly notable extension of rank-maximality, a notion ntroduced by Irving et al. Our second algorithm computes in polynomial time optimal k-assignments with respect to the aforementioned fairness function.

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)

Database transformations provide a unifying view for queries and updates, the two fundamental types of computations in any databases capturing the capability to retrieve and update data. The integration of queries and updates has always been a research challenge in database theory. The emerging new application areas such as web-based systems and service-oriented architectures have further increased the importance of this problem. Recently, it was shown that non-deterministic database transformations can be captured exactly by a variant of Abstract State Machines (ASMs), the so-called Database Abstract State Machines (DB-ASMs). In this talk I will present a logic for DB-ASMs. in spite of bounded non-determinism permitted by DB-ASMs, the logic for DB-ASMs is proven to be sound and complete when the logic of meat-finite states is parameterised by the first-order logic. This is due to the finiteness condition stipulated on the database part of a state of database transformations, which thereby leads to the finiteness of update sets and multisets in one-step transitions. We can then formalise non-determinism of DB-ASMs by utilising a modal operator [] for an update set of multiset generated by a DB-ASM rule. The logic for DB-ASMs lies down a solid foundation for developing verification techniques to study the properties of database transformations in various data-intensive applications.

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)

We introduce a derivative of Dung's seminal abstract argumentation frameworks (AFs) through which distinctive features both of Dung's semantics and so-called ``value-based'' argumentation frameworks (VAFs) may be captured. These frameworks, which we describe as mixed AFs, thereby recognise that, in some circumstances, arguments may be deemed acceptable, not only as a consequence of subjective viewpoints (as are modelled by the concept of audience in VAFs) but also as a consequence of ``value independent'' acceptance of other arguments: for example in the case of factual statements. We analyse divers acceptability conditions for arguments in mixed AFs. These may be be formulated independently of any specific extension-based semantics, so that variants considering preferred, semi-stable, resolution-based etc are possible. We, further, obtain a complete picture for the computational complexity of the associated decision questions in both preferred and semi-stable cases. This analysis has two surprising consequences: reasoning in mixed AFs poses significantly greater computational challenges than either standard or value-based questions, a number of problems being complete at the third level of the polynomial-time hierarchy (as opposed to worst-case second-level completeness results in standard AFs). Secondly, mixed credulous reasoning questions are as demanding as mixed sceptical reasoning (in preferred semantics) and, under standard assumptions, can even be harder (in semi-stable semantics).

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)

The aim of this tutorial is to give an introduction into social choice theory with special emphasis on tools of general relevance developed in this area (as extensions of rankings of objects to sets and distance-based approaches) and recent extensions (e.g. judgment aggregation).

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)

Many application areas (e.g., concerning the semantic web or biological applications) consider graph structured data, where the data consists of a finite set of nodes connected by labeled edges. For querying such data one usually needs to specify types of paths along which nodes are connected. A widely studied class of queries for graph structured databases are the conjunctive regular path queries, where types of paths can be described by regular expressions specifying labels along the paths. For modern applications, however, also more expressive query languages are desirable, allowing not only to specify regular properties of path labels, but also to compare paths based on, e.g., their lengths, labels, or similarity. The aim of this talk is to give an overview of recent developments in this area. Special emphasis will be put on query languages, their expressive power, and their complexity concerning query evaluation and static analysis. With kind support of the Wolfgang Pauli Institut (WPI).

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)
• Thematic program: Logic based reasoning and data mining on the web (2012)

This talk addresses belief revision where the underlying logic is that governing Horn clauses. It proves to be the case that classical (AGM) belief revision doesn't immediately generalise to the Horn case. In particular, a standard construction based on a total preorder over possible worlds may violate the accepted (AGM) postulates. Conversely, Horn revision functions in the obvious extension to the AGM approach are not captured by total preorders over possible worlds. We address these difficulties by first restricting the semantic construction to ``well behaved'' orderings; and second, by augmenting the revision postulates by an additional postulate. This additional postulate is redundant in the AGM approach but not in the Horn case. In a representation result we show that these two approaches coincide. Arguably this work is interesting for several reasons. It extends AGM revision to inferentially-weaker Horn theories; hence it sheds light on the theoretical underpinnings of belief change, as well as generalising the AGM paradigm. Thus, this work is relevant to revision in areas that employ Horn clauses, such as deductive databases and logic programming, as well as areas in which inference is weaker than classical logic, such as in description logic.

• Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)
• Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)