Decidable Theories of the Ordering of Natural Numbers with Unary Predicates | Zendy

Alexander Rabinovich | Zendy; Wolfgang Thomas | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Decidable Theories of the Ordering of Natural Numbers with Unary Predicates

Author(s) -

Alexander Rabinovich,

Wolfgang Thomas

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-45458-6

DOI - 10.1007/11874683_37

Subject(s) - unary operation , decidability , successor cardinal , expressive power , monadic predicate calculus , second order logic , binary relation , computer science , automaton , first order logic , semigroup , rotation formalisms in three dimensions , discrete mathematics , mathematics , natural number , order (exchange) , theoretical computer science , description logic , higher order logic , mathematical analysis , finance , economics , geometry

Expansions of the natural number ordering by unary predicates are studied, using logics which in expressive power are located between 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 conditions 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 analogous results are obtained in the semigroup theoretic and the automata theoretic framework.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research