The color coding means:

: all participate
: Doctoral students participate

Please find the abstracts below the schedule and note that some of the slides are made available here, internally.

All seminars sessions can be accessed via a zoom link that will be provided in due time. The passcodes will be sent around via email. 

The passcodes to the virtual meetings can also be inquired from Sandy Seifarth.

Abstracts

Rafael Peñaloza: Semiring-based Provenance for Light-weight Description Logics

Semiring-based provenance was originally studied in database theory to assign additional semantics to facts, and to the query answers that can be derived from them. This approach has been recently extended to ontologies, assigning a provenance token to each axiom in the ontology. Consequences from this ontology inherit a provenance value represented by a polynomial. In this talk, we present this provenance approach over light-weight description logics, showing that its semantics presents several difficulties for handling conjunctions. Assuming multiplicative idempotency mitigates these issues and allows for effective reasoning methods. In particular, we present a new automata-based construction for answering simple provenance queries in a variant of the DL EL.

Corto Mascle: Keyboards as a new model of computation

In this talk I will present a new formalisation of languages, called keyboards. A keyboard K is a finite set of keys, which are finite sequences of elementary operations, such as writing/erasing a letter, going one position to the right or the left... The language of K is the set of words obtained by applying a sequence of keys on an initially empty writing space.

We can define various classes of languages based on the set of elementary operations we consider, and compare their expressive powers between them, and to well-known classes of languages.

The main interests of keyboards are, first that from a deceiptively simple model we obtain many deep and complex (and fun!) mathematical questions, and second that their expressivity is interestingly orthogonal to the ones of classical models like finite automata or context-free algebras.

Cosimo Persia: On the Exact Learnability of Possibilistic Theories

We investigate learnability of possibilistic theories from entailments in light of Angluin's exact learning model. We consider cases in which only membership, equivalence, or both membership and equivalence queries can be posed by the learner. We prove non-learnability of possibilistic logic theories when the learner can ask only membership queries and it does not know how much information is needed to represent every uncertainty degree of the target. In every other case, learnability is guaranteed. We then show that, for a large class of learning problems, polynomial time learnability results for classical logic can be transferred to the respective possibilistic extension. We also show that the converse direction always holds.
In particular, it follows from our results that the possibilistic extension of propositional Horn theories is exactly learnable in polynomial time. As polynomial time learnability in the exact model is transferable to the classical probably approximately correct (PAC) model, our work also establishes such results in this model. Finally, we discuss how possibilistic theories can be used to model imprecise probabilities.

Thomas Eiter: Semiring Extension of Answer Set Programs and Sum-of-Product Problems

Weighted Logic is a powerful tool for specifying calculations over semirings that depend on qualitative information. This offers the possibility to express quantitative measures of many different natures and to approach respective reasoning problems such as probabilistic reasoning, preferential reasoning and quantitative queries in a uniform manner. In this talk, we shall review recent work on an extension of Answer Set Programming (ASP) with semiring computations, in which weighted formulas are evaluated over the answer sets of a logic program such that the reasoning problems above are supported. Notably, some quantitative extensions of ASP can be formalized using semiring computations, as well as the well-known Problog formalism. The complexity of program evaluation apparently depends much on the the complexity of the underlying semiring, which in turn depends on its representation; under natural conditions, the evaluation problem is in FPSPACE(poly). We then consider the evaluation of specific semiring expressions, namely sum-of-product expressions (SOP), to which many problems such as SAT, #SAT, and probabilistic inference amount. SOPs can be characterized by NP(R), a novel generalization of NP over a semiring R, which links to well-known complexity classes.

joint work with Rafael Kiesel

Nikolai Käfer: Semantics for Bayesian Networks with Cycles

Traditional Bayesian networks are directed acyclic graphs that are widely used for representing expert knowledge with uncertainties. However, directed cycles can naturally arise when cross-dependencies between random variables exist, e.g., for modeling feedback loops. Existing methods to deal with such cross-dependencies rely on reductions to Bayesian networks without cycles. These approaches are fragile to generalize, since their justifications are intermingled with the application context.
In this talk, I will present semantics for cyclic Bayesian networks which conservatively extend the cycle-free setting and are agnostic of the application context. We look into constraints to enforce consistency with given conditional probability tables, independencies implied by the graph structure, and a notion of cutsets for cyclic BNs. Perhaps surprisingly, Markov chain analysis will prove to be useful for the definition of the main semantics.

The talk is based on recently submitted joint work with Christel Baier, Holger Hermanns and Clemens Dubslaff.

Benedikt Pago: Computation in Finite Model Theory: Symmetric Algorithms and their Limitations

One of the central topics in finite model theory is the complexity of symmetric computation. From the point of view of “classical“ complexity theory, it might seem odd that symmetry should play a role at all in computation. In fact, if we consider Turing machines, it doesn’t. By contrast, from the perspective of logic, there are other natural ways to define computation models, and these are symmetry-invariant. Important examples are transitive-closure logic, fixed-point logic, and Choiceless Polynomial Time. In these frameworks, computations do not manipulate ordered binary strings, but unordered finite structures; for instance, graphs. The main  difference to Turing machines is that logics do not have the ability to choose arbitrary elements from the input but may only handle definable (isomorphism-invariant) subsets of the structure in each step. The study of symmetric computation models leads to a more fine-grained view on classical complexity classes such as PTIME because it brings the parameter “choice“ into the picture. This has a nice benefit: While it is generally hard to show the non-existence of efficient algorithms for a problem, in the symmetry-invariant setting we actually do have useful tools to prove lower bounds. These include pebble games and the analysis of automorphism groups. In this talk, I will give a general introduction to the subject and also present some of my own research on lower bounds for the logic Choiceless Polynomial Time.

Albert Vucaj: Finite structures modulo primitive positive constructability

We compare finite structures according to the primitive positive (pp) constructability order. Our main motivation is that pp constructability preserves the complexity of the Constraint Satisfaction Problems.  In the 70's Post fully described the lattice of two-element structures modulo pp definability. In this talk I will present a complete description of the lattice of two-element structures modulo pp constructability and some results about properties of the pp constructability poset in the general case.​

Caterina Viola: The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains

Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over infinite-domains. This extends a result of Brakensiek and Guruswami [SODA’20] for promise (non-valued) CSPs (on finite domains).
Joint work with Stanislav Živný.

Jan Křetínský: Learning-based LTL synthesis

In LTL synthesis, the task is to construct a reactive system producing an output stream ensuring a given formula of linear temporal logic is satisfied for any input stream. Recent results on translating LTL to automata open avenues to learning-based approaches and heuristics for such problems. In particular, the automata-theoretic approach to LTL synthesis can utilize not only topological information through standard graph algorithms, but can now also profit from semantic information through learning algorithms. As a result, in many cases an optimal solution can be obtained without any computation; in more general cases, the approach might yield more explainable controllers and scale better.

Bartosz Bednarczyk: Forward Guarded Fragment: A tamed higher-arity extension of ALC

During the talk I will present a novel logic called the forward guarded fragment (FGF) that combines ideas of forward and guarded quantification.
The presented logic extends the Description Logic ALC with higher-arity relations in a tamed way: both the knowledge base satisfiability problem and conjunctive query entailment problem are ExpTime-complete, thus having the same complexity as plain ALC. We provide a few intuitions behind these results and discuss an ongoing work towards model-theory and extensions of FGF.

Ismail Ceylan: Explanations for Ontology-Mediated Query Answers

Ontologies are logical theories that formalize domain-specific knowledge, thereby allowing for reasoning over a particular domain. A popular paradigm in this context is ontology-mediated query answering, which aims at improving query answers over (incomplete) data sources with the use of an ontology. In this paradigm, a query (e.g., conjunctive query) is coupled with an ontology, called an ontology-mediated query, and evaluated over a database, leading to a more complete set of answers. The focus of this talk is on explaining answers to ontology-mediated queries: given an ontology-mediated query and a database, an explanation is viewed as a minimal subset of the database that entails the input query. Based on this notion of an explanation and a choice of a minimality criterion, a variety of explanation problems, such as recognizing a single explanation, recognizing all explanations, recognizing a relevant or necessary fact in an explanation will be discussed, along with selected complexity results. We will provide an overview of explanations under different minimality criteria, showing how the results are affected by a particular choice of minimality criteria. While the talk will focus on existential rules as ontology languages, we will also show how these results translate to description logics. We will touch upon the dual task of deriving explanations for negative query answers, i.e., the task of explaining ontology-mediated queries that are not entailed from the database. We will conclude with some open problems and challenges within the broader context of explainable artificial intelligence.

References:

[1] İ. İ. Ceylan‚ T. Lukasiewicz‚ E. Malizia and A. Vaicenavičius. Explanations for Query Answers under Existential Rules, IJCAI 2019.
[2] İ. İ. Ceylan‚ T. Lukasiewicz‚ E. Malizia and A. Vaicenavičius. Explanations for Ontology−Mediated Query Answering in Description Logics, ECAI 2020.
[3] İ. İ. Ceylan‚ T. Lukasiewicz‚ E. Malizia‚ C. Molinaro and A. Vaicenavičius. Explanations for Negative Query Answers under Existential Rules, KR 2020.
[4] İ. İ. Ceylan‚ T. Lukasiewicz‚ E. Malizia‚ C. Molinaro and A. Vaicenavičius. Preferred Explanations for Ontology−Mediated Queries under Existential Rules, AAAI 2021.

Paul Gastin: Weighted Tiling Systems for Graphs: Evaluation Complexity

We consider weighted tiling systems to represent functions from graphs to a commutative semiring such as the Natural semiring or the Tropical semiring. The system labels the nodes of a graph by its states, and checks if the neighbourhood of every node belongs to a set of permissible tiles, and assigns a weight accordingly. The weight of a labeling is the semiring-product of the weights assigned to the nodes, and the weight of the graph is the semiring-sum of the weights of labelings. We show that we can model interesting algorithmic questions using this formalism - like computing the clique number of a graph or computing the permanent of a matrix. The evaluation problem is, given a weighted tiling system and a graph, to compute the weight of the graph. We study the complexity of the evaluation problem and give tight upper and lower bounds for several commutative semirings. Further we provide an efficient evaluation algorithm if the input graph is of bounded tree-width.