We consider deterministic automata which accept vectors of d integers for a fixed positive integer d. A deterministic automaton is then a finite representation of the sets of vectors it accepts. Many operations are particularly efficient with this representation, such as intersection of sets, testing whether two sets are equal or deciding whethersuch an automaton accepts a Presburger-definable set, that is a FO[+,<]-definable set over integers. We consider a similar problem for less expressive logics such as FO[<,0,moda] or \FO[+1,0,mod], where mod is the class of modular relations.

We state that it is decidable in time O(nlog(n)) whether a set of vectors accepted by a given finite deterministic automaton can be defined in the less expressive logic. The case of dimension 1 was already proven by Marsault and Sakarovitch. If the first algorithms gives a positive answer, the second one computes in time O(n^{3}log(n)) an existential formula in this logic that defines the same set. This improves the 2EXP time algorithm that can be easily obtained by combining the results of Leroux and Choffrut.

In this talk, it is intended to: -Introduce automata reading vectors of integers, -Present the logic FO[<,0,mod] over integers -Introduce classical tools relating automata to numbers. -Give an idea of how they can be applied to the above-mentionned problem.