Seminars

Speaker: Sophie Tison

Title: Containment of Regular Path Queries Under Constraints

Speaker: Pierre Lermusiaux (plermusi.github.io/)

Title: Detection of Uncaught Exceptions in Functional Programs by Abstract
Interpretation

Abstract:

Exception handling is a key feature in modern programming languages. Exceptions
can be used to deal with errors, or as a means to control the flow of execution
of a program. Since they might unexpectedly terminate a program, unhandled
exceptions are a serious safety concern. We propose a static analysis to detect
uncaught exceptions in functional programs, that is defined as an abstract
interpreter. It computes a description of the values potentially returned by a
program using a novel abstract domain, that can express inductively defined
sets of values. Simultaneously, the analysis infers the possibly raised
exceptions, by computing in the abstract exception monad. This abstract
interpreter has been implemented as an effective static analyser for a large
subset of OCaml programs, that supports mutable data types, the OCaml module
system, and dynamically extensible data types such as the exception type. The
analyser has been evaluated on several hundreds of OCaml programs.

Titre: Direct Access for Conjunctive Queries with Negation
Abstract:
Direct Access is the operation of returning, given an index j, the jth answer of a conjunctive query on a given database for a given order. 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 set of a query Q that takes polylogarithmic time in the size of the database after a polynomial time precomputation. Previous work has precisely characterised the tractable classes and given fined-grained lower bounds on the time needed for precomputation depending on the structure of the query. We give a generalisation 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 direct access task 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 circuits. We recover the known tractable classes from the literature in the case of positive conjunctive queries using this technique and also discover new islands of tractability for signed conjunctive queries. In particular, our result generalises to the Direct 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 joint work with Florent Capelli.

TBA