program-v4.2-a5

Full program in PDF



Monday 11 September

8:15-8:50    Welcome Coffee and Registration

8:50-9:00    Conference Opening

9:00-10:00   Invited Talk: Anca Muscholl (Bordeaux)   (Chair: Marc Zeitoun)

              A Tour of Recent Results on Word Transducers.

10:00-10:20  Coffee break

10:20-12:00  Automata & Logic   (Chair: Jérôme Leroux)

  • Christof Löding and Christopher Spinrath.
    Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words.
  • Pierre Ganty and Elena Gutiérrez.
    Parikh Image of Pushdown Automata.
  • Emmanuel Filiot, Nicolas Mazzocchi and Jean-François Raskin.
    Decidable Weighted Expressions with Presburger Combinators.
  • Kord Eickmeyer and Ken-Ichi Kawarabayashi.
    FO Model Checking on Map Graphs.

12:00-13:40  Lunch (in building "Haut-Carré", room "Badiane")

13:40-14:40  Invited Talk: Martin Dietzfelbinger (Ilmenau)   (Chair: Jyrki Katajainen)

              Optimal Dual-Pivot Quicksort: Exact Comparison Count.

14:40-15:30  Routing Algorithms   (Chair: Jyrki Katajainen)

  • Indranil Banerjee and Dana Richards.
    New Results on Routing via Matchings on Graphs.
  • Till Fluschnik, Marco Morik and Manuel Sorge.
    The Complexity of Routing with Few Collisions.

15:30-15:50  Coffee break

15:50-17:05  Algorithms   (Chair: Aris Pagourtzis)

  • Gianluca De Marco, Tomasz Jurdziński, Michał Różański and Grzegorz Stachowiak.
    Subquadratic Non-adaptive Threshold Group Testing.
  • Markus Blaeser, B. V. Raghavendra Rao and Jayalal Sarma.
    Testing Polynomial Equivalence by Scaling Matrices.
  • Maxime Crochemore, Alice Héliou, Gregory Kucherov, Laurent Mouchard, Solon Pissis and Yann Ramusat.
    Minimal Absent Words in a Sliding Window & Applications to On-Line Pattern Matching.

17:05-17:15  Short pause

17:15-18:05  Formal Languages   (Chair: Holger Petersen)

  • Max Kanovich, Stepan Kuznetsov and Andre Scedrov.
    Undecidability of the Lambek Calculus Extended with Subexponential and Bracket Modalities.
  • Joost Engelfriet and Andreas Maletti.
    Multiple Context-free Tree Grammars and Multi-Component Tree Adjoining Grammars.

18:05-18:30  Business Meeting

18:45-19:00  Conference Picture

19:00-21:00  Welcome Cocktail, Salle Badiane, Haut-Carré (cross the street behind the lab building).



Tuesday 12 September

8:30-9:00   Welcome Coffee

9:00-10:00  Invited Talk: Jean-Éric Pin (Paris). Talk in memory of Zoltán Ésik   (Chair: Pascal Weil)

              Some Results of Zoltán Ésik on Regular Languages.

10:00-10:20  Coffee break

10:20-12:00  Models of Computation & Complexity   (Chair: Hugo Gimbert)

  • Jérémie Cabessa and Olivier Finkel.
    Expressive Power of Evolving Neural Networks Working on Infinite Input Streams.
  • Holger Petersen.
    Busy Beaver Scores and Alphabet Size.
  • Pushkar Joglekar, B. V. Raghavendra Rao and Siddhartha Sivakumar.
    On Weak-Space Complexity over Complex Numbers.
  • Alexander Shen.
    Automatic Kolmogorov Complexity and Normality Revisited.

12:00-13:40  Lunch (in building "Haut-Carré", room "Badiane")

13:40-14:40  Invited talk: Juraj Hromkovič (Zürich)   (Chair: Ralf Klasing)

              What One Has to Know when Attacking P vs. NP.

14:40-15:30  Best Papers   (Chair: Ralf Klasing)

  • Matthias Bentert, Till Fluschnik, André Nichterlein and Rolf Niedermeier.
    Parameterized Aspects of Triangle Enumeration. Best student paper
  • Albert Atserias, Phokion Kolaitis and Simone Severini.
    Generalized Satisfiability Problems via Operator Assignments. Best paper

15:30-15:50  Coffee break

15:50-17:05  Graph Algorithms   (Chair: Marthe Bonamy)

  • Nicolas Bousquet, Aline Parreau and Arnaud Mary.
    Token Jumping in Minor-Closed Classes.
  • Charis Papadopoulos and Spyridon Tzimas.
    Polynomial-time Algorithms for the Subset Feedback Vertex Set Problem on Interval Graphs and Permutation Graphs.
  • George Manoussakis.
    Listing all Fixed Length Simple Cycles in Sparse Graphs in Optimal Time.

18:30-23:00 Social event and banquet (Map)

Wednesday 13 September

8:30-9:00   Welcome Coffee

9:00-10:00  Invited Talk: Thomas Colcombet (Paris)   (Chair: Marc Zeitoun)

              Automata and Program Analysis.

10:00-10:25  Tropical Algebra   (Chair: Marc Zeitoun)

  • Dima Grigoriev and Vladimir Podolskii.
    Tropical Combinatorial Nullstellensatz and Fewnomials Testing.

10:25-10:45  Coffee break

10:45-12:25  Quantum Computation & Boolean Functions   (Chair: Cyril Gavoille)

  • Luc Sanselme and Simon Perdrix.
    Determinism and Computational Power of Real Measurement-based Quantum Computation.
  • Anurag Anshu, Peter Høyer, Mehdi Mhalla and Simon Perdrix.
    Contextuality in Multipartite Pseudo-Telepathy Graph Games.
  • Endre Boros, Ondrej Cepek and Kazuhisa Makino.
    Strong Duality in Horn Minimization
  • Christian Engels, B. V. Raghavendra Rao and Karteek Sreenivasaiah.
    On Σ∧Σ∧Σ Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree.

12:25-14:05  Lunch (in building "Haut-Carré", room "Badiane")

14:05-15:45  Distributed Algorithms & Mobile Agents   (Chair: Arnaud Casteigts)

  • Aris Pagourtzis, Giorgos Panagiotakos and Dimitris Sakavalas.
    Reliable Communication via Semilattice Properties of Partial Knowledge.
  • Tomasz Jurdzinski and Michał Różański.
    Deterministic Oblivious Local Broadcast in the SINR Model.
  • Andreas Bärtschi and Thomas Tschager.
    Energy-Efficient Fast Delivery by Mobile Agents.
  • Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska, Paweł Żyliński.
    The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents).

15:45-16:00  Conference closing and Coffee