 |
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é) |
Organizing Committee
Comité d’organisation Nadia Creignou (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. |
Meghyn Bienvenu (CNRS, Université de Bordeaux) Introduction to description logic ontologies: syntax, semantics, relation to other logics, basic reasoning tasks
Anatole Dahan (Université de Paris) Towards a logic for PTIME group computations
Arnaud Durand (Université de Paris) Recursion schemes, discrete differential equations and characterization of polynomial time computation
Lauri Hella (Tampere University) Generalized quantifiers and their EF-games
Juha Kontinen (University of Helsinki) Complexity aspects of logics in team semantics
Yasir Mahmood (Leibniz University Hannover) Counter claim augmented argumentation framework
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
Claudia Nalon (University of Brasilia) Extensions and combinations: the logics in the modal cube; fusions and products
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
 |
 |