Computability of extender sets in multidimensional subshifts
1 : GREYC
Université 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.