Logically defined subsets of Nk

AbstractWe give a characterization, in terms of a restriction of semi-simple sets, of the class of subsets of Nk definable in an extension of first-order logic obtained by adjoining quantifiers which count modulo an integer. It is shown that this class strictly contains the class of recognizable subsets of Nk and is strictly contained in the class of rational subsets of Nk. We also characterize the subsets of Nk which are definable in the usual first-order logic and in the first-order logic which uses only the special modular quantifiers. A characterization of the subsets of Nk definable in the first-order theory of the successor function and the = predicate is also given. Links with the parallel complexity class ACC0 are discussed