Direct Access is the operation of returning, given an index j, the j-th answer of a conjunctive query Q on a given database for some given order on the answers set of Q. While this problem is #P-hard in general (wrt combined complexity), many conjunctive queries are structured enough so that for some lexicographical ordering of their answers, one can have a direct access to the answer of Q that takes polylogarithmic time in the size of the database after polynomial time precomputation. Previous work have precisely characterized the tractable classes and given fine grained lower bounds on the time needed for precomputation depending on the structure of the query. We give a generalization of these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on solving the ranked access for a class of circuits that can represent relational data. Our result then follows from the fact that the tractable (signed) conjunctive queries can be transformed into polynomial size circuit. We recover the known tractable classes from the literature in the case of positive conjunctive queries using this technique and also discover new island of tractability for signed conjunctive queries. In particular, our result generalizes to the Ranked Access Problem the known tractabilities of counting the number of answers to beta-acyclic negative queries and of deciding whether a negative query with bounded nested-width has an answer. This is join work with Oliver Irwin and appeared at ICDT 2024:

- ArXiv version: https://arxiv.org/abs/2310.15800 - Published version: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.13

In this talk we are interested in the problem of learning linear temporal logic (over finite traces, LTL_f) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. We initiate the study of the computational complexity of the problem. Our main results are hardness results: we show that the LTL_f learning problem is NP-complete for almost all of its fragments, but also hard to approximate within a o(log n) factor in some cases. This motivates the search for efficient heuristics, and highlights the complexity of expressing separating properties in concise natural language.

A question was asked 35 years: can we store an infinite set in a database? Turns out the answer is yes, and for this a set has to be finitely representable. In databases we use logic for querying, and thus finitely represent sets by logical formulas over infinite models. The next question was: what can you ask about such databases? To answer this question we had to go back to the finite world, and thus embedded finite models were born, a mix of finite and the infinite. While theoreticians were happy to talk about AC0 and o-minimality, cell decomposition, and local triviality in the same paper, practitioners asked whether something useful can be built based on these ideas. The 1990s answer was no, computers were too slow, solvers were too immature. But the world doesn’t stand still, and we have witnessed signs of rebirth of this area that at the very least gave us theoreticians lots of fun. In the talk I’ll tell this story and share some thoughts on making finitely representable databases great again.

We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. In a first part I'll explain how Vilar's algorithm for the active learning à la Angluin of (normal) transducers generalize to monoidal transducers. In a second part I'll then discuss how this is an instance of the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile: the active learning algorithm was obtained by instantiating monoidal transducers in this framework.

This talk focuses on automatic (aka synchronous) relations, defined as the binary relations of finite words that can be recognized by finite-state synchronous automata. We study two orthogonal approaches.

- Graph theoretic properties: we show that given an automatic graph (a graph defined by an automatic relation), the problem of whether the graph can be regularly 2-coloured (meaning that it can be 2-coloured, and for every colour, the set of words having this colour is a regular language) is surprisingly undecidable; this results yields the undecidability of the separation problem of automatic relations by a subclass of recognizable relations.

- Language-theoretic properties: on the contrary, we show that most of the reasonable language-theoretic properties of automatic relations are decidable. We develop an algebraic theory for automatic relations, called “synchronous algebras”, which are to relations as monoids are to languages. The three pillars of algebraic language theory hold in our settings, namely (1) all relations admit a syntactic synchronous algebra, which is finite if and only if the relation is automatic, (2) classes of automatic relations with nice closure properties (called pseudovarieties) are in natural correspondence with pseudovarieties of finite synchronous algebras and (3) the latter are exactly the classes of finite synchronous algebras which can be described by “profinite dependencies”, a generalization of classical profinite equations. Building on these results, we show how algebraic characterizations of pseudovarieties of regular languages can be lifted to the pseudovarieties of synchronous relations that they induce.

The graph-colourability part the talk is based on a joint work with Pablo Barceló and Diego Figueira published at MFCS '23.

We review the different ways tractability is defined in enumeration using as complexity measure total time, incremental time, delay and space. We present the associated complexity classes, typical problems and algorithmic methods.

The focus is on understanding incremental polynomial time and polynomial delay which are the classes containing most problems. In particular we present an attempt to classify which saturation problems naturally in incremental polynomial time are in fact in polynomial delay and give separation and collapses for general classes. We also briefly present low complexity classes and way to completely avoid exhaustive enumeration, through compact representation and approximation of the solution set.

In two-player turn-based stochastic parity games, both players have positional optimal strategies. On the other hand, in two-player concurrent parity games, optimal strategies may not exist and playing (almost-)optimally may require infinite memory. In this talk, I will present how to identify a local condition that ensures the existence of positional optimal strategies for both players; this local condition is satisfied by more than only turn-based games. I will discuss how we have proved this result — by adapting to the concurrent setting techniques used in the turn-based deterministic setting — and what we can say about this local condition.

This is a joint work with my former PhD advisors Patricia Bouyer and Stéphane Le Roux, and it is based on a paper published in CSL 2024.

Description Logics (DLs) are a family of logic-based knowledge representation formalisms with appealing computational properties and various applications at the confluence of artificial intelligence, databases and other areas. In particular, DLs are well-suited for representing and reasoning about ontologies; therefore, they stand as the formal foundations of the Semantic Web. The different DL formalisms that have been proposed in the literature provide us with a wide choice of constructors in the object language. Nevertheless, these are intended to represent only classical, unquestionable knowledge and, therefore, cannot express and cope with the different aspects of uncertainty and vagueness that often appear in everyday life. Examples of these comprise the various guises of exceptions, typicality (and atypicality), approximations and many others, as usually encountered in the different forms of everyday human reasoning. A similar argument can be put forward when moving to the level of entailment, that of the sanctioned conclusions from an ontology. DL systems provide a variety of (standard and non-standard) reasoning services. Still, the underlying notion of entailment remains classical. Therefore, depending on the application one has in mind, DLs inherit most of the criticisms raised in the development of the so-called non-classical logics. In this talk, I make a case for endowing DLs and their associated reasoning services with the ability to cope with defeasibility. I start by introducing the notion of defeasible class subsumption, which allows for the specification of and reasoning about defeasible inheritance. I also show how it can be given an intuitive semantics in terms of preference relations. Next, I show how to take defeasibility to the level of entailment through the notion of rational closure of a defeasible ontology. Of particular interest is the fact that our constructions do not negatively affect the decidability or complexity of reasoning with defeasible inheritance for a wide class of DLs.

Speaker's short CV: Ivan Varzinczak is an associate professor at Université Paris 8. He holds a PhD (2006) in artificial intelligence from Université Paul Sabatier, France. Ivan has co-authored over 75 peer-reviewed publications on logic-based approaches to knowledge representation and reasoning in AI. In 2019 he defended his habilitation at Université d'Artois, France. Ivan is an associate editor of Artificial Intelligence and of the Journal of Artificial Intelligence Research and chairman of the steering committee of the International Workshop on Nonmonotonic Reasoning. In 2022, he served as program chair of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS). He has had several visiting researcher appointments and taught courses and tutorials worldwide, including two courses at ESSLLI and two tutorials at IJCAI.

Ésik and Kuich extended the theory of weighted formal languages to infinite words in 2005. There, automata are matrices over a semiring and Büchi acceptance is an operation over those matrices. We are trying to extend the theory to other acceptance conditions (Muller, generalized Büchi, etc.) and face several challenges. Mainly, the former operator allows for a disjunction of constraints but now we need conjunction.

I will introduce the theory and detail those challenges.

Joint work with Uli Fahrenberg.

Often, a formal language can be described in several ways. The different descriptions bring with them different perspectives. One constraint might appear to be complex by one analysis but simple under another. This talk discusses a few of the classes that have arisen with good motivation in the study of natural languages, with perspectives from algebra and learning theory in addition to the languages and their automata.

Distributed systems are ubiquitous and their implementation is complex and error-prone. In order to check for errors, they can be modeled as systems of communicating automata, where each automaton represents the behavior of an element of the system. In general, verification problems are undecidable in such a model. The use of (under or over) approximations is necessary. This talk presents k-synchronizable systems, which are a subclass of systems of communicating automata, and some results on them.

Dynamic algorithms constitute an established and rich research area. “Dynamic Complexity” refers to a much less known research area, in which dynamic algorithms are specified by formulas of first-order logic. The class of problems for which this is possible is called DynFO.

The talk gives a short introduction to Dynamic Complexity and presents a recent and ongoing line of research that tries to bring Dynamic Complexity closer to Dynamic Algorithms through the study of constant-time parallel dynamic algorithms. It also takes a look at constant-time parallel “static” algorithms.

Automata can be characterized in terms of their expressive power, as well as their learnability, i.e. under what cases a canonical representation can be induced from data. This talk will overview recent insights in the learnability of subclasses of the regular transductions. I will overview polynomial time learning algorithms in a variety of settings, and show how in some cases one can reduce even further in time and space for certain subclasses (those that coincidentally characterize natural language patterns). I will then show how classes of functions can be used to create rigorous experiments testing the learning capacity of sequential neural networks. If there is time I will overview some ongoing work connecting newer neural net varieties to aperiodic transducers.