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)
- 18:30-19:30: Guided visit in the city centre. Meeting point: Place de la Bourse (see Map).
- 20:00-23:00 Banquet dinner at restaurant Café du Port (1 Quai Deschamps, Bordeaux).
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).
