Invited Speakers
Kevin Perrot
Kevin Perrot (website)
Aix-Marseille Université
Invited talk: Sandpile models and P-completeness
Sandpile models are number conserving cellular automata, where grains move from cell to cell according to local rules. On finite grids it has a beautiful algebraic structure with a mysterious identity element. The “complexity” of such models can be studied through the algorithmic hardness of predicting the dynamics, which is feasible in polynomial time simply by simulating the whole stabilization process of grains move. From a theoretical point of view, whether it is possible or not to do better, i.e. predict sandpiles in logarithmic time on parallel machines (PRAM), is still open. This corresponds to the complexity class NC (Nick’s Class), which is not known to be equal or differ from P (neither to be equal of differ from NP), hence there is a notion of P-completeness. We will discuss circuit value problem (CVP, the canonical P-complete problem), its variants and connections with sandpiles. All this will be presented while playing with a sandpile simulator.
Dora Giammarresi (website)
Università di Roma “Tor Vergata”
Invited talk: Isometric words and edit distance
Isometric words combine the notion of edit distance together with properties of words of not appearing as factors in other words. An edit distance is a metric between words that quantifies how two words differ by counting the number of edit operations needed to transform one word into the other one. A word \(f\) is said isometric with respect to an edit distance if, for any pair of \(f\)-free words \(u\) and \(v\), there exists a transformation of minimal length from \(u\) to \(v\) via the related edit operations such that all the intermediate words are also \(f\)-free. The adjective “isometric” comes from the fact that, if the Hamming distance is considered (i.e., only replacement operations are used), then isometric words are connected with definitions of isometric subgraphs of hypercubes. We discuss known results and some interesting generalizations together with open problems.