Provability of the Pigeonhole Principle and the Existence of Infinitely Many Primes. - Jeff B. Paris; A. J. Wilkie; Alan R. Woods (J. Symb. Log., 1988)

Exponential Lower Bounds for the Pigeonhole Principle - Paul Beame; Russell Impagliazzo; Jan Krajícek; Toniann Pitassi; Pavel Pudlák; Alan R. Woods (STOC, 1992)

Decidability and Undecidability of Theories with a Predicate for the Primes. - P. T. Bateman; Carl G. Jockusch Jr.; Alan R. Woods (J. Symb. Log., 1993)

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle - Jan Krajícek; Pavel Pudlák; Alan R. Woods (Electron. Colloquium Comput. Complex., 1994)

Approximating the structures accepted by a constant depth circuit or satisfying a sentence-a nonstandard approach. - Alan R. Woods (Logic and Random Structures, 1995)

An Exponenetioal Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle. - Jan Krajícek; Pavel Pudlák; Alan R. Woods (Random Struct. Algorithms, 1995)

Counting Finite Models. - Alan R. Woods (J. Symb. Log., 1997)

Coloring rules for finite trees, and probabilities of monadic second order sentences. - Alan R. Woods (Random Struct. Algorithms, 1997)

Unsatisfiable Systems of Equations, Over a Finite Field. - Alan R. Woods (FOCS, 1998)

The number of Boolean functions computed by formulas of a given size. - Petr Savický; Alan R. Woods (Random Struct. Algorithms, 1998)

A New Proof of the Weak Pigeonhole Principle. - Alexis Maciel; Toniann Pitassi; Alan R. Woods (J. Comput. Syst. Sci., 2002)

Subset sum "cubes" and the complexity of primality testing. - Alan R. Woods (Theor. Comput. Sci., 2004)

On bounded arithmetic augmented by the ability to count certain sets of primes. - Charalampos Cornaros; Alan R. Woods (J. Symb. Log., 2009)

Some Natural Zero One Laws for Ordinals Below ε 0. - Andreas Weiermann; Alan R. Woods (CiE, 2012)