Bibliography Kevin J. Compton and C. Ward Henson . A uniform method for proving lower bounds on the computational complexity of logical theories. Selected papers that cite this one Patrick Cegielski, Yuri Matiyasevich, and Denis Richard. Definability and decidability issues in extensions of the integers with the divisibility predicate.
Exact complexity bounds for ordinal addition.
Ehrenfeucht games and ordinal addition. The theory of integer multiplication with order restricted to primes is decidable. Non-elementary lower bound for Propositional Duration Calculus. IEEE Computer Society Press.