Guest Editorial: Special Issue on Theoretical Aspects of Computer Science (2017)

International audienceThis special issue contains seven articles which are based on extended abstracts that were presented at the 34th Symposium on Theoretical Aspects of Computer Science (STACS), which was held at the Leibnizhaus in Hannover from March 8th to 11th, 2017. These extended abstracts were chosen among the top papers of those that were selected for presentation at STACS 2017 in a highly competitive peer-review process (after which only 54 papers out of 212 submissions were accepted). Compared with the original extended abstracts, the articles have been extended with a description of the context, full proofs and additional results. They underwent a further rigorous reviewing process, following the TOCS Journal standard, completely independent from the selection process of STACS 2017. The topics of the chosen papers cover combinatorics on words, circuit complexity , computational geometry, (parameterized) algorithms for graph problems , Markov chains, and stochastic games. The article On Long Words Avoiding Zimin Patterns by Arnaud Carayol and Stefan Göller extends a classical result on combinatorics on words concerning unavoidable patterns, so called Zimin patterns. The authors study the question of the smallest length (depending on alphabet size) of a word that guarantees that a certain pattern appears-a very active research area in recent years. The main contribution here is a non-elementary lower bound on some of these minimal lengths