Activities This Week

In a deductive game for two players, SF and PGOM, SF conceals an n-digit number $x = x_1, ..., x_n,$ and PGOM, who knows n, tries to identify x by asking a number of questions, which are answered by SF. Each question is an n-digit number $y = y_1, ..., y_n$; each answer is a number a(x, y), the number of subscripts i such that $x_i = y_i$. Moreover we require the questions from PGOM are predetermined.

In this talk, I will show that the minimum number of questions required to determine x is (2+o(1))n / log n. A more general problem is to determine the asymptotic formula of the metric dimension of Cartesian powers of a graph.

I will state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.

Joint work with Nikita Polyanskii.

Topologial conjugacy is most probably the most natural notion of isomorphism for topological dynamical systems. Classifying subshifts of finite type up to topological conjugacy is a notoriously hard problem with a long history of results. Much less is known about the corresponding problem for endomorphisms of subshifts of finite type (aka cellular automata). I will discuss necessary and sufficient criteria under which periodic cellular automata are topologically conjugate. The main tool will be derivative algebras in the sense of Tarski and McKinsey, an algebraic structure based on the Cantor-Bendixson derivative.