Decidable Theories of the Ordering of Natural Numbers with Unary Predicates Dedicated to Boris A. Trakhtenbrot on the occasion of his 85th birthday
Alexander Rabinovich, Wolfgang H Thomas · 2006
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.