Guest Editorial: Special Issue on Theoretical Aspects of Computer Science (2017) - GREYC amacc Access content directly
Journal Articles Theory of Computing Systems Year : 2019

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

Abstract

This 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.
Fichier principal
Vignette du fichier
PrefaceSIStacs2017---copie.pdf (138.08 Ko) Télécharger le fichier

Dates and versions

hal-02735297 , version 1 (09-06-2020)

Identifiers

Cite

Heribert Vollmer, Brigitte Vallée. Guest Editorial: Special Issue on Theoretical Aspects of Computer Science (2017). Theory of Computing Systems, 2019, 63 (5), pp.923-925. ⟨10.1007/s00224-019-09934-y⟩. ⟨hal-02735297⟩
69 View
30 Download

Altmetric

Share

Gmail Facebook X LinkedIn More