Thursday, July 13, 2017

[DMANET] FCT 2017 - Early registration ends on July 16th


*** Second Call for Participation ***

FCT 2017

21st International Symposium on
Fundamentals of Computation Theory

September 11-13, 2017
Bordeaux, France


*** Registration is now open at
*** Early registration: July 16, 2017.



The Symposium on Fundamentals of Computation Theory (FCT) was established in 1977 for researchers interested in all aspects of theoretical computer science, and in particular algorithms, complexity, formal and logical methods. FCT is a biennial conference. The last preceding Symposia were held in Gdansk, Liverpool, Oslo, Wrocław, Budapest, Lübeck.

FCT 2017 will take place in Bordeaux, which is located in the South West of France. The region is famous for its wines and its gastronomy. The city centre of Bordeaux is classified at the Unesco World Heritage.


There will be four invited talks at FCT 2017. The invited speakers are:

- Thomas Colcombet (CNRS, Université Paris Diderot, France).
- Martin Dietzfelbinger (Technische Universität Ilmenau, Allemagne).
- Juraj Hromkovic (ETH Zürich, Suisse).
- Anca Muscholl (Université de Bordeaux, France).

There will also be one invited talk in memoriam of Zoltan Esik given by:

- Jean-Eric Pin (CNRS, Université Paris Diderot, France).

ACCEPTED PAPERS (in submission order)

1. Christof Löding and Christopher Spinrath. Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words
2. Max Kanovich, Stepan Kuznetsov and Andre Scedrov. Undecidability of the Lambek calculus extended with subexponential and bracket modalities
3. Endre Boros, Ondrej Cepek and Kazuhisa Makino. Strong Duality in Horn Minimization
4. Joost Engelfriet and Andreas Maletti. Multiple Context-free Tree Grammars and Multi-Component Tree Adjoining Grammars
5. George Manoussakis. Listing all fixed length simple cycles in sparse graphs in optimal time
6. Emmanuel Filiot, Nicolas Mazzocchi and Jean-François Raskin. Decidable Weighted Expressions with Presburger Combinators
7. Holger Petersen. Busy Beaver Scores and Alphabet Size
8. Pierre Ganty and Elena Gutiérrez. Parikh Image of Pushdown Automata
9. Matthias Bentert, Till Fluschnik, André Nichterlein and Rolf Niedermeier. Parameterized Aspects of Triangle Enumeration
10. Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska and Paweł Żyliński. The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)
11. Anurag Anshu, Peter Høyer, Mehdi Mhalla and Simon Perdrix. Contextuality in multipartite pseudo-telepathy graph games
12. Alexander Shen. Automatic Kolmogorov complexity and normality revisited
13. Tomasz Jurdzinski and Michał Różański. Deterministic Oblivious Local Broadcast in the SINR Model
14. Jérémie Cabessa and Olivier Finkel. Expressive Power of Evolving Neural Networks Working on Infinite Input Streams
15. 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
16. Luc Sanselme and Simon Perdrix. Determinism and Computational Power of Real Measurement-based Quantum Computation
17. Nicolas Bousquet, Aline Parreau and Arnaud Mary. Token Jumping in minor-closed classes
18. Christian Engels, Raghavendra Rao B V and Karteek Sreenivasaiah. On depth five Sum-Power-Sum-Power-Sum Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree.
19. Albert Atserias, Phokion Kolaitis and Simone Severini. Generalized Satisfiability Problems via Operator Assignments
20. Till Fluschnik, Marco Morik and Manuel Sorge. The Complexity of Routing with Few Collisions
21. Pushkar Joglekar, Raghavendra Rao B V and Siddhartha Sivakumar. On Weak-Space Complexity over Complex Numbers
22. Dima Grigoriev and Vladimir Podolskii. Tropical Combinatorial Nullstellensatz and Fewnomials Testing
23. Gianluca De Marco, Tomasz Jurdziński, Michał Różański and Grzegorz Stachowiak. Subquadratic Non-adaptive Threshold Group Testing
24. Aris Pagourtzis, Giorgos Panagiotakos and Dimitris Sakavalas. Reliable communication via semilattice properties of partial knowledge
25. Indranil Banerjee and Dana Richards. New Results On Routing Via Matchings On Graphs
26. Markus Blaeser, Raghavendra Rao B V and Jayalal Sarma. Testing Equivalence of Polynomials under Scaling
27. Charis Papadopoulos and Spyridon Tzimas. Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
28. Andreas Bärtschi and Thomas Tschager. Energy-efficient fast delivery by mobile agents
29. Kord Eickmeyer and Ken-Ichi Kawarabayashi. FO Model Checking on Map Graphs


For more details, please visit the FCT 2017 website: (now open for registration).

For further information, please send an e-mail

* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.