2011/09/27 by Fabien Durand, Durand, Fabien, Michel Rigo +1
Computer Science · #semigroups and automata theory #Computability, Logic, AI Algorithms #Algorithms and Data Compression
paper · doi:10.48550/arxiv.1109.5801
A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence x over a finite alphabet is ultimately periodic if and only if, for some n, the number of different factors of length n appearing in x is less than n+1. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let d≥ 2. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of \ZZd definable by a first order formula in the Presburger arithmetic . With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse--Hedlund theorem to an arbitrary dimension d and characterize sets of \ZZd definable in in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.