› Invited speakers › Program › Abstracts › Local info › Organisation › Contact

The next Journée(s) GT DAAL will take place 21 April 2023, just before ETAPS, at EPITA Paris in Kremlin-Bicêtre, in Amphi 0.

Invited Speakers

Participants

List of participants

Program

Friday 21 April
8:45 Opening
9:00 Marie Van Den Bogaard Invited talk: Subgame-perfect equilibria in multiplayer games
9:45 Corentin Barloy Progress on weak validation of streamed trees
10:05 Coffee etc.
10:35 Philipp Schlehuber-Caissier Strategy learning from timed automata
10:55 Nguyễn Lê Thành Dũng Revisiting the growth of polyregular functions
11:15 Corto Mascle Model-checking lock-sharing systems with tree automata
11:35 Break
11:45 Florent Koechlin Invited talk: Weakly unambiguous Parikh automata and their link to holonomic series
12:30 Lunch
14:00 Kim G. Larsen Keynote talk: Extensions and applications of dependency graphs and equation systems
15:00 Noam Zeilberger Invited talk: Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem
15:45 Théo Matricon Program synthesis by examples
16:05 Coffee etc.
16:35 Liat Peterfreund Invited talk: Querying incomplete numerical data: between certain and possible answers
17:20 Anantha Padmanabha Algorithms for consistent query answering under primary key constraints
17:40 Rémi Morvan Approximation and semantic tree-width of conjunctive regular path queries
18:00 Closing

Registration

Registration is now closed. If you have not registered but want to attend, send an email to uli@lrde.epita.fr and we'll see what we can do.

Local information

The journée takes place at EPITA Paris, in Kremlin-Bicêtre just outside Porte d'Italie, in Amphi 0 at the ground floor. Public transportation access:

For lunch we will go to Hotel Campanile, 200 meters from EPITA.

Abstracts

Marie Van Den Bogaard: Subgame-perfect equilibria in multiplayer games

Multiplayer games on graphs are a powerful tool to model rich reactive systems. In this model, each player has its own objective, which can coincide or not with the ones of the other players. We then speak of non zero-sum games, and we look at solution concepts for this setting. Most famous of them, the Nash Equilibrium, makes the assumption that the players are rational, to a certain extent. Indeed, one shortcoming of this concept is the tolerance for non-credible threats : players may, in some scenarios, plan behaviours that are no longer taking their own objectives into account. In this talk, we focus on a refinement of Nash Equilibria : Subgame Perfect Equilibria, which make the assumption that players behave rationally in all possible scenarios. We propose a general approach to solve the Non-cooperative Rational Synthesis Problem: given a multiplayer game and a distinguished player $P$, does there exist a strategy for this player that is winning in every scenario where the others play rationally?
This is joint work with Véronique Bruyère (Université de Mons, BE), Jean-François Raskin and Alexis Reynouard (Université libre de Bruxelles, BE).

Corentin Barloy: Progress on weak validation of streamed trees

This is about ongoing research. Processing tree-structured data (like XML) in the streaming model is a challenge. In this work, we assume that all the documents represents correct trees and we only focus on validating properties. Segoufin and Vianu raised the problem of deciding whether a regular property can be validated in constant space. We conjecture that there is a trichotomy: either a document can be validated: i) in constant space ii) in logarithmic space and not in sub-logarithmic space iii) in linear space and not in sub-linear space. We propose some leads that involve the algebraic theory of regular tree languages: the framework of tree algebras introduced by Bojańczyk and Walukiewicz. This gives partial result, as which commutative regular properties can be validated in constant space.

Philipp Schlehuber-Caissier: Strategy learning from timed automata

In this work we use a pipeline for verifiable learning of cooperative timed strategies. We show how to train a machine learning based model from verifiable data obtained from timed automata runs which are refined using SMT based techniques before being used as data. On a side-note we also discuss associated decidability and performance issues which derived from our model using stopwatches.

Nguyễn Lê Thành Dũng: Revisiting the growth of polyregular functions

The class of polyregular functions is composed of the string-to-string functions computed by pebble transducers. While this machine model (which extends two-way finite transducers) is two decades old, several alternative characterizations of polyregular functions have been discovered since 2018, demonstrating their canonicity. The name comes from the polynomial bound on the growth rate of these functions: $|f(w)| = |w|^{O(1)}$ where $|w|$ is the length of the string $w$.
In this talk, after recalling this context, I will present some results that either relate the growth rate of a polyregular function (perhaps belonging to some subclass) to the "resources" needed to compute it, or show that there is no such relationship. Some of these results were first shown by Bojańczyk, but we propose significantly simplified proofs.
This is joint work with Sandra Kiefer and Cécilia Pradic, see the unfinished preprint https://arxiv.org/abs/2301.09234 (and Bojańczyk's paper https://arxiv.org/abs/2212.11631).

Corto Mascle: Model-checking lock-sharing systems with tree automata

We consider a parameterized model of distributed systems where pushdown processes may spawn new processes, and synchronisation is enforced by locks that can be created and passed to spawned processes. Runs of such systems can be represented as trees, and there is an automaton recognising trees representing runs of a given system. This gives an algorithm to check various regular properties of runs under strong fairness condition.

Florent Koechlin: Weakly unambiguous Parikh automata and their link to holonomic series

I will talk about the connection between unambiguity in automata theory and the properties of the generating series of their associated languages. It is a classical result that regular languages have rational generating series and that unambiguous context-free languages have algebraic series. In the eighties, several consequences of this link have been studied: for instance, Philippe Flajolet developed efficient tools based on generating series to prove easily the inherent ambiguity of many context-free languages; and Stearns and Hunt developed a polynomial-time algorithm for the inclusion problem on unambiguous finite automata, based on the rationality of their associated series.
I will present how these ideas relying on generating series can be extended to Parikh automata. This is joint work with Alin Bostan, Arnaud Carayol and Cyril Nicaud.

Noam Zeilberger: Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem

I will discuss a categorical perspective on context-free languages, in which context-free grammars are described by certain functors of operads. Besides permitting simpler and more conceptual formulations of various properties of CFGs, this perspective naturally generalizes to define context-free languages of arrows in any category, including categories of runs of finite-state automata. The main result of the MFPS paper is a generalization of the Chomsky-Schützenberger representation theorem, whose classical statement says that any context-free language may be represented as the homomorphic image of the intersection of a Dyck language with a regular language. We found that at the heart of this theorem is a surprising adjunction between categories and operads, where the right adjoint W : Cat -> Oper builds the "operad of spliced arrows" W[C] of a category, whose operations are certain sequences arrows in C, while the left adjoint C : Oper -> Cat builds the "contour category" C[O] of an operad, whose arrows have a geometric interpretation as oriented contours of operations in O.
Based on joint work with Paul-André Melliès and a paper of the same title that appeared at MFPS 2022 (https://doi.org/10.46298/entics.10508).

Théo Matricon: Program synthesis by examples

Program Synthesis by examples is the task of generating a program given examples of inputs output pairs that satisfies the examples. A program has the advantage of being interpretable both by humans and machine, as such it can also be checked. The space of programs, described by a grammar, becomes exponentially bigger as depth increases. We propose to limit this growth making use of tree automata to describe the constraints about the task at hand. Furthermore, we also propose to enhance our programs as knowledge-powered programs using knowledge graphs (or databases) so that our programs can use knowledge about the world and not only the one defined in the grammar.

Liat Peterfreund: Querying incomplete numerical data: between certain and possible answers

Queries with aggregation and arithmetic operations, as well as incomplete data, are common in real-world databases, but we lack a good understanding of how they should interact. On the one hand, systems based on SQL provide ad-hoc rules for numerical nulls, on the other, theoretical research largely concentrates on the standard notions of certain and possible answers which in the presence of numerical attributes and aggregates are often meaningless.
In this work, we define a principled compositional framework for databases with numerical nulls and answering queries with arithmetic and aggregations over them. We assume that missing values are given by probability distributions associated with marked nulls, which yields a model of probabilistic bag databases. We concentrate on queries that resemble standard SQL with arithmetic and aggregation and show that they are measurable, and that their outputs have a finite representation. Moreover, since the classical forms of answers provide little information in the numerical setting, we look at the probability that numerical values in output tuples belong to specific intervals. Even though their exact computation is intractable, we show efficient approximation algorithms to compute such probabilities.
The talk is based on joint work with Marco Console and Leonid Libkin, and will be presented at PODS 2023.

Anantha Padmanabha: Algorithms for consistent query answering under primary key constraints

Databases often have constraints. One of the basic constraints is the "primary key constraint" which states there can be at most one tuple for every primary key. However, these days it is common to have databases that violate such constraints which is called an "inconsistent database". In particular, if a database violates primary key constraint, it will contain more than one tuple for the same primary key. In this setting, the notion of a repair is defined by picking exactly one tuple for each primary key (maximal consistent subset of the database). A Boolean conjunctive query $q$ is certain for an inconsistent database $D$ if $q$ evaluates to true over all repairs of $D$. In this context, we have a dichotomy conjecture that states that for a fixed boolean conjunctive query $q$, testing whether $q$ is certain for an input database $D$ is either polynomial time or coNP-complete.
The conjecture is open in general, but has been verified for self-join-free and path queries. However, the polynomial time algorithms known in the literature are complex and use different strategies in the two cases. We propose a simple inflationary fixpoint algorithm for consistent query answering which correctly computes certain answers when the query q falls in the polynomial time cases for self-join-free queries and path queries. This raises a natural question, whether this algorithm works for all polynomial time cases. We answer this negatively and show that there are polynomial time certain queries (with self-joins) which cannot be computed by such an algorithm. These results were obtained in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo and was presented at ICDT'23.

Rémi Morvan: Approximation and semantic tree-width of conjunctive regular path queries

Conjunctive Regular Path Queries (CRPQs) form an expressive query language on edge-labeled graphs (a.k.a. graph databases) whose core feature is to allow the user to query the existence of a path whose label belongs to some regular language. While the problem of, given a graph database and a CRPQ, to decide if the query holds on this database is NP-complete, it becomes polynomial-time solvable when restricted to classes queries of bounded tree-width. This begs the following question: given a CRPQ, can we decide if it is equivalent to a CRPQ of tree-width k? In 2013, Barceló, Romero and Vardi gave a positive answer to this question for the case $k=1$. In this work, we show that the problem is also decidable for every $k\ge 2$. This is joint work with Diego Figueira, published at ICDT 2023.

Organisation

Sponsors

                               

Contact

uli@lrde.epita.fr