Decidable Theories of the Ordering of Natural Numbers with Unary Predicates Dedicated to Boris A. Trakhtenbrot on the occasion of his 85th birthday

Expansions of the natural number ordering by unary predi- cates are studied, using logics which in expressive power are located be- tween first-order and monadic second-order logic. Building on the model- theoretic composition method of Shelah, we give two characterizations of the decidable theories of this form, in terms of effectiveness condi- tions on two types of homogeneous sets. We discuss the significance of these characterizations, show that the first-order theory of successor with extra predicates is not covered by this approach, and indicate how anal- ogous results are obtained in the semigroup theoretic and the automata theoretic framework.