The 2018 annual meeting of GT ALGA has taken place in Université de Lille on October 15 and 16.

Keynote speakers

Meghyn Bienvenu

Ontology-mediated query answering: Harnessing knowledge to get more from data


Abstract: Recent years have seen an increasing interest in ontology-mediated query answering (OMQA), in which the semantic knowledge provided by an ontology is exploited when querying data. Adding an ontology has several advantages (e.g. simplifying query formulation, integrating data from different sources, providing more complete answers to queries), but it also makes the query answering task more difficult. Query rewriting, which reduces OMQA to the evaluation of database queries, is a key algorithmic technique that allows OMQA to be implemented on top of existing database systems, thereby benefitting from the maturity and performance of such systems.

In this talk, I will give a short introduction to ontology-mediated query answering, focusing on ontologies formulated using description logics. Then I will consider two natural analysis tasks related to query rewriting (concerning the existence and succinctness of rewritings) and present solutions obtained by leveraging connections to different areas of theoretical computer science (namely, circuit complexity, automata, and constraint satisfaction).

Pierre Marquis

On Definability for Model Counting (joint work with Jean-Marie Lagniez and Emmanuel Lonca)


Abstract: We define and evaluate a new preprocessing technique for propositional model counting. This technique leverages definability, i.e., the ability to determine that some gates are implied by the input formula F. Such gates can be exploited to simplify F without modifying its number of models. Unlike previous techniques based on gate detection and replacement, gates do not need to be made explicit in our approach. Our preprocessing technique thus consists of two phases: computing a bipartition (I,O) of the variables of F where the variables from O are defined in F in terms of I, then eliminating some variables of O in F. Our experiments show the computational benefits which can be obtained by taking advantage of our preprocessing technique for model counting.

Victor Marsault

Formal semantics of Cypher : towards a standard language for querying property graphs


Abstract: Cypher is a query languages for databases that are structured as property graphs. It was originally implemented as part of the proprietary graph database Neo4j and it is now widely used in industry. Cypher was designed to be easily readable and usable by non-experts. As a result, the semantics of Cypher queries is described using natural language and the expected result is often ambiguous. Our work aims at defining a full denotational semantics of Cypher, in order to pave the way for a future open standard.


Abstracts and slides of the talks can be found in the program page.

Monday Salle des conseils, bâtiment M3, 1er étage
10:30-11:30 Pierre Marquis On Definability for Model Counting
11:30-12:00 Sylvain Salvati Free word order, word problem in groups and context-freeness
12:00-12:30 Nathanaël Fijalkow Parity games and universal graphs
12:30-14:00 Lunch break
14:00-15:00 Victor Marsault Formal semantics of Cypher: towards a standard language for querying property graphs
15:00-16:00 Coffee break
16:00-16:30 Pierre Ohlmann Characterization of non-associative circuits using automata, and applications
16:30-17:00 Vadim Malvone Agents with Visibility-Control
17:00-17:30 Discussions on GT Alga.
Tuesday Salle des conseils, bâtiment M3, 1er étage
09:30-10:30 Meghyn Bienvenu Ontology-mediated query answering: Harnessing knowledge to get more from data
10:30-11:00 Coffee break
11:00-11:30 Marie Van den Bogaard Beyond admissibility: Dominance betweens chains of strategies
11:30-12:00 Amazigh Amrane Logic and rational languages of scattered and countable series-parallel posets
12:00-12:30 Elisa Orduna Deciding preservation of normality for transducers
12:30 Lunch


To help us with the organization, please register to the meeting by sending an email to florent(dot)capelli(at)univ-lille(dot)fr. The registration is free.

Practical informations

The talk will be delivered in building M3 in Cité Scientifique, see map below. The talk will take place in "Salle des Conseils". Both rooms are on the first floor of M3 building.

To reach the site from the city center or the station, you will have to take the Métro line 1 (the yellow line) to Cité Scientifique, Professeur Gabillard.

Registered participants

  1. Amarilli Antoine
  2. Amrane Amazigh
  3. Bienvenu Meghyn
  4. Boiret Adrien
  5. Bourhis Pierre
  6. Boneva Iovka
  7. Capelli Florent
  8. Crosetti Nicolas
  9. Dartois Luc
  10. Exibard Léo
  11. Fijalkow Nathanaël
  12. Grandjean Étienne
  13. Grosshans Nathan
  14. Hallet Marion
  15. Malvone Vadim
  16. Marquis Pierre
  17. Marsault Victor
  18. Mazowiecki Filip
  19. Monet Mikaël
  20. Niehren Joachim
  21. Ohlmann Pierre
  22. Orduna Elisa
  23. Paperman Charles
  24. Penelle Vicent
  25. Ramanathan Varun
  26. Salvati Sylvain
  27. Serre Olivier
  28. Tison Sophie
  29. Van den Bogaard Marie