GT ALGA – Annual Meeting 2016

Program

We will welcome three keynote speakers:

• Pierre Bourhis (CNRS, CRIStAL, Université de Lille): Tree Automata for Reasoning in Databases and Artificial Intelligence
  Abstract: In database management, one of the principal task is to optimize the queries to evaluate them efficiently. It is in particular the case for recursive queries for which their evaluation can lead to crawl all the database. In particular, one of the main question is to minimize the queries in order to avoid to evaluate useless parts of the query. The core theoretical question around this line of work is the problem of inclusion of a query in another. Interestedly, this question is related to an important question in IA which is to answer a query when the data is incomplete but rules are given to derive new information. This problem is called certain query answering. In both context, if both problem are undecidable in general, there are fragments based on guardedness that are decidable due to the fact there exists witness of the problems that have a bounded tree width and that their encoding in trees is regular. Furthermore, the queries can be translated in MSO. In both contexts, Courcelle’s Theorems imply the decidability of both problems. I will present to the different results on the translation of logic class of formula for our problems into tree automata to obtain tight bounds to the problems of inclusion of recursive queries or certain query answering.
• Stefan Göller (CNRS, LSV, ENS Cachan): Reachability of subclasses of (branching) vector addition systems
  Abstract: I will survey some of the recent results on the reachability and coverability problem for subclasses of (branching) vector addition systems with states. The talk will include a PSPACE-completeness result for the reachability of two-dimensional vector addition systems with states, closing a doubly-exponential complexity gap and PTIME-completeness of the reachability problem for unary branching vector addition systems with states, hereby establishing a first decidability result for reachability of (a subclass of) branching vector addition systems.
• Helmut Seidl (Technische Universität München): Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
  Abstract: Top-down tree-to-string transducers recursively process their structured input data while producing output in an unstructured way, namely as a string. Let yDT denote the class of all deterministic top-down tree-to-string transducers. In the presentation, we show that equivalence of two such transducers is decidable - a problem which has been open for more than 30 years. As non-equivalence can be witnessed by an input on which the two transducers differ, decidability of equivalence follows if only an effective proof system can be provided for certifying equivalence whenever it holds. We indicate how such a proof system can be constructed using powerful techniques from commutative algebra. While in general not much is known about the complexity of the decision problem, we also present special cases where polynomial upper bounds can be obtained. [Joint work with Sebastian Maneth (Edinburgh) and Gregor Kemper (München).]

Monday 11 April

Welcome coffee from 10:00 to 10:30

Session 1

• 10:30-11:00 Béatrice Bérard (LIP6, Université Pierre et Marie Curie): Verification of Polynomial Interrupt Timed Automata
• 11:00-11:30 Daniel Stan (LSV, ENS Cachan): Reachability in Networks of Register Protocols under a Fair Stochastic Scheduler
• 11:30-12:30 Keynote: Stefan Göller (CNRS, LSV, ENS Cachan): Reachability of subclasses of (branching) vector addition systems

Lunch

Session 2

• 14:00-15:00 Keynote: Pierre Bourhis (CNRS, CRIStAL, Université de Lille): Tree Automata for Reasoning in Databases and Artificial Intelligence
• 15:00-15:30 Olivier Serre (IRIF, Université Paris Diderot): Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings

Coffee break

Session 3

• 16:00-16:30 Olivier Carton (IRIF, Université Paris Diderot): Transfinite Lyndon Words
• 16:30-17:00 Nathan Lhote (LaBRI, Université de Bordeaux): Towards an Algebraic Theory of Rational Word Functions
• 17:00-17:30 Nathanaël Fijalkow (University of Oxford): The Theory of Regular Cost Functions At No Extra Cost

Discussion after 17:30

Dinner at 20:00

Tuesday 12 April

Session 4

• 9:00-9:30 Antoine Durand-Gasselin (LIF, Aix-Marseille Université): Regular Transformations of Data Words Through Origin Information
• 9:30-10:00 Laure Daviaud (LIP, ENS Lyon): A Generalised Twinning Property for Minimisation of Cost Register Automata
• 10:00-10:30 Félix Baschenis (LaBRI, Université de Bordeaux): Ressource Minimization and One-Way Definability of Two-Way Transducers

Coffee break

Session 5

• 11:00-12:00 Keynote: Helmut Seidl (Technische Universität München): Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

Lunch

Session 6

• 13:30-14:00 Denis Kuperberg (Technische Universität München): Good-for-Games Automata
• 14:00-14:30 Rodica Condurache (LACL, Université Paris-Est Créteil): The Complexity of Rational Synthesis
• 14:30-15:00 Stéphane Le Roux (Université libre de Bruxelles): Extending Finite Memory Determinacy

Coffee break

Session 7

• 15:30-16:00 Joanna Ochremiak (Universitat Politècnica de Catalunya): Homomorphism Problems for First-Order Definable Structures
• 16:00-16:30 Bastien Maubert (Università degli Studi di Napoli Federico II): Relating Paths in Transition Systems: The Fall of the Modal mu-Calculus
• 16:30-17:00 Florent Capelli (IMJ, Université Paris Diderot): Compilation of CNF-formulas: New Algorithms and Lower Bounds

Practical Information

The meeting will take place at Aix-Marseille Université, on Campus Saint-Charles (5 minutes of the train station of Marseille), in Amphi Charve (see on the map of the campus) from 11 April at 10:00, to 12 April at 17:00.

Registrations are closed, but contact the organisers by email if you still want to join. A dinner will be organised on Monday 11 April.

You may choose every hotel in the neighbourhood of Vieux Port or the place of the meeting. We can direct you towards the following selection (available on the CNRS platform for booking) with an estimation of rates:

• Best Western: Hôtel Marseille Bourse Vieux Port: ***, approximately 75€ per night with breakfast
• Hôtel Carré Vieux Port: ***, approximately 90€ per night with breakfast
• Massili'Appart Vieux Port: **, approximately 80€ per night for a small studio with breakfast
• Holiday Inn Express Marseille - Saint Charles: ****, approximately 80€ per night with breakfast (closer to the train station and the meeting, but further from the Vieux Port)

The meeting is organised by Jean-Marc Talbot, Pierre-Alain Reynier, Benjamin Monmege, and Antoine Durand-Gasselin. Contact them for any question regarding the meeting by email.

List of registered participants

• Félix Baschenis, LaBRI
• Pierre Bourhis, CNRS CRIStAL UMR 9189
• Damien Busatto-Gaston, LIF, ENS Cachan
• Béatrice Bérard, LIP6, UPMC
• Florent Capelli, IMJ-PRG, Paris 7
• Mathieu Caralp
• Olivier Carton, IRIF, Université Paris Diderot
• Rodica Condurache, LACL, Universite Paris-Est Créteil, Université libre de Bruxelles
• Laure Daviaud, LIP, ENS Lyon
• Catalin Dima, LACL, Université Paris-Est Créteil
• Antoine Durand-Gasselin, LIF, Centrale Marseille
• Nathanaël Fijalkow, University of Oxford
• Etienne Grandjean, GREYC, Université Caen Normandie
• Pierre Guillon, Institut de Mathématiques de Marseille
• Bruno Guillon, IRIF, Université Paris Diderot, Paris 7
• Madhur Gupta, LIF, Thapar University
• Stefan Göller, LSV, ENS Cachan
• Ismaël Jecker, Université libre de Bruxelles
• Denis Kuperberg, TU Munich
• Stephane Le Roux, Université libre de Bruxelles
• Jérôme Leroux, LaBRI, CNRS
• Nathan Lhote, LaBRI, Université de Bordeaux
• Bastien Maubert, University of Naples
• Benjamin Monmege, LIF, Aix-Marseille Université
• Joanna Ochremiak, UPC Barcelona
• Frédéric Olive, AMU
• Youssouf Oualhadj, LACL (U-PEC)
• Pierre-Alain Reynier, LIF, AMU, CNRS
• Ocan Sankur, CNRS Irisa
• Mathieu Sassolas, LACL, Université Paris-Est Créteil
• Helmut Seidl, Technische Universität München
• Olivier Serre, IRIF (Univ. Paris Diderot, CNRS)
• Daniel Stan, LSV, ENS Cachan
• Jean-Marc Talbot, LIF, Aix-Marseille Université
• Guillaume Theyssier, I2M (CNRS, AMU)
• Alexandre Vigny, IMJ, Université Paris Diderot
• Didier Villevalois, LIF
• El Makki Voundy, LIF, Aix-Marseille Université

Sponsors