Logic, databases and complexity: new methods and challenges (Thematic Month 2022)

CIRM, Luminy, Marseille

Date(s) : 14/02/2022 - 18/02/2022   iCal
0 h 00 min



Logic, databases and complexity: new methods and challenges
Logique, bases de données et complexité : nouvelles méthodes et challenges
14 – 18 February 2022
Scientific Committee
Comité scientifique
Nadia Creignou (Aix-Marseille Université)
Arnaud Durand (Université de Paris)
Heribert Vollmer (Leibniz University Hannover)
Organizing Committee
Comité d’organisation
Nadia Creignou (Aix-Marseille Université)
Frédéric Olive (Aix-Marseille Université)
This workshop aims at revisiting the interplay between logic, databases and complexity.
It is well-known for years that these domains are intimately related. For example, since the 70’s fragments of first-order and second-order logic have been involved both in description of computational problems and in expression of database queries. Logic has thus provided insights into complexity issues and has strengthened the theoretical framework of databases programming languages.
In the recent years, several new concepts have revivified these connections. Team-based logics are some of them. Their semantic is based on the evaluation of a first-order formula not for a single assignment to its free variables, but for sets of such assignments, so called teams. On the syntactic side the logical language is extended with team atoms, which allow to specify properties of teams. One such property is the functional dependency, which explains the importance of team-based logics for databases.
The workshop will provide an informal venue to discuss new connections and challenges that renew the interaction between logic, complexity and databases.
L’objectif de ce workshop est de revisiter les interactions entre logique, bases de données et complexité.
On connait depuis longtemps les liens intimes que ces domaines entretiennent. Par exemple, depuis les années 70, divers fragments des logiques du premier et du second ordres ont été invoqués dans la description des problèmes combinatoires ou dans l’expression des requêtes. La logique a ainsi contribué à clarifier des questions de complexité et à étayer les fondements théoriques des langages de requête.
Ces dernières années, de nouveaux concepts ont revivifié ces connexions. Parmi eux, les logiques basées sur les team sémantiques. Ces sémantiques sont fondées sur l’évaluation d’une formule du premier ordre par des ensembles d’affectations de valeurs à ses variables, les “teams”, plutôt que par une unique affectation. Du point de vue syntaxique, la logique du premier ordre est étendue avec des “team atoms”, qui permettent de spécifier des propriétés singulières des teams, au premier rang desquelles celle de dépendance fonctionnelle – d’où l’importance de ces logiques pour les bases de données.
Le workshop prendra la forme d’une rencontre informelle pour discuter des nouvelles connexions et des défis qui renouvellent les interactions entre logique, complexité et bases de données.
Our goal is to foster interaction by having several invited talks, introductory or specialist tutorials, and presentations selected only on the basis of brief submitted abstracts.


Meghyn Bienvenu (CNRS, Université de Bordeaux)    Introduction to description logic ontologies: syntax, semantics, relation to other logics, basic reasoning tasks
Lauri Hella (Tampere University)    Generalized quantifiers and their EF-games 
Juha Kontinen (University of Helsinki)    Complexity aspects of logics in team semantics 
Claudia Nalon (University of Brasilia)     Extensions and combinations: the logics in the modal cube; fusions and products
Arne Meier (Leibniz University Hannover)     Parameterized complexity in dependence logic
Stefan Mengel (CNRS, Université d’Artois de Lens)     Tight Fine-Grained Bounds for Direct Access on Join Queries
Nicola Olivetti  (Aix-Marseille Université)     Non-normal modal logics
Reinhard Pichler (Technical University of Vienna)    Introduction to relational query languages and Codd’s Theorem
Jonni Virtema (University of Sheffield)    New developments in temporal team semantics 




Retour en haut 

Secured By miniOrange