Séminaire Algorithmique : « Computability of extender sets in multidimensional subshifts », Léo Paviet Salomon (GREYC, Caen)

A classical result from the theory of formal languages, the Myhill-Nerode theorem, gives a necessary and sufficient condition in terms of congruence classes for a language to be regular. In this talk, we try to adapt this result to the case of subshifts, in which we consider potentially multidimensional infinite configurations rather than finite words. In particular, we study the behavior of /extender entropy/, a property introduced by R. Pavlov and T. French which is analogous to congruence classes in formal languages, and obtain some computability characterizations on the possible extender entropies of various classes of subshifts.