6th Workshop on Logic, Language, Information and Computation
May 25-28, 1999
(Tutorial Day: May 25th)

Hotel Simon, Itatiaia National Park, Rio de Janeiro, Brazil

Scientific Sponsorship
Interest Group in Pure and Applied Logics (IGPL)
European Association for Logic, Language and Information (FoLLI)
Association for Symbolic Logic (ASL)
Sociedade Brasileira de Computação (SBC)
Sociedade Brasileira de Lógica (SBL)

CAPES, CNPq, Facoltà di Scienze, Univ. di Verona

Departamento de Informática, Universidade Federal de Pernambuco (DI-UFPE)

Facoltà di Scienze, Università degli Studi di Verona (Sci-Univr
Centro de Lógica, Epistemologia e História da Ciência, Univ. Campinas (CLEHC-UNICAMP)

Alan R. Woods

Current Position

Honorary Research Fellow, Department of Mathematics, University of Western Australia.

Former Positions

  • Assistant Professor, Dept. of Mathematics, Yale University, 1985-89.
  • Lecturer in Mathematics, University of Malaya, 1982-85.


  • B.Sc.(Hons. 1), University of Queensland, 1971-74.
  • M.Sc., Monash University, 1975-78.
  • Ph.D., University of Manchester, 1978-81. (Holder of a Bishop Harvey Goodwin Mathematical Scholarship.)

    Research Interests

    Weak axiom systems and nonstandard models for arithmetic; finite model theory; computational complexity, especially of circuits, formulas and propositional proofs; connections between logic, combinatorics and number theory; infinite permutation groups.

    Selection of Published Work

  • Unsatisfiable systems of equations, over a finite field. To appear in: Proceedings of the 39th Annual Symposium on Foundations of Computing, IEEE (1998).
  • (With P. Savický) The number of Boolean functions computed by formulas of a given size. To appear in: Random Structures Algorithms (1998).
  • Counting finite models. Journal of Symbolic Logic, 62 (1997) 925-949.
  • Coloring rules for finite trees, and probabilities of monadic second order sentences. Random Structures Algorithms, 10 (1997) 453-485.
  • Approximating the structures accepted by a constant depth circuit or satisfying a sentence - a nonstandard approach. In: Logic and Random Structures, R. B. Boppana, J. F. Lynch (eds), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 33 (1997) 109-130.
  • (With J. Krajícek and P. Pudlák.) An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures Algorithms, 7 (1995) 15-39.
  • (With M. Brazil, J. Covington, T. Penttila, C. E. Praeger.) Maximal subgroups of infinite symmetric groups. Proc. London Math. Soc. (3), 68 (1994) 77-111.
  • (With P. T. Bateman and C. G. Jockusch.) Decidability and undecidability of theories with a predicate for the primes. Journal of Symbolic Logic, 58 (1993) 672-687.
  • (With P. Beame, R. Impagliazzo, J. Krajícek, T. Pitassi, P. Pudlák.) Exponential lower bounds for the pigeonhole principle. Proceedings of the 24th Annual ACM Symposium on Theory of Computing, (1992) 200-220.
  • (With J. B. Paris, A. J. Wilkie.) Provability of the pigeonhole principle and the existence of infinitely many primes. Journal of Symbolic Logic 53 (1988), 1235-1244.

    Last modified: April 28, 1999, 15:36:50 GMT-0300.