Albert R. Meyer

Research Interests

Professional Positions

• Feb, 1991: Appointed Hitachi America Professor of Engineering
• 1969-: Professor of Computer Science, Department of EECS, MIT
• 1978-1979: Visiting Professor, Division of Applied Science, Harvard University
• 1967-1969: Assistant Professor of Computer Science, Computer Science Department, Carnegie-Mellon University

Professional Activities

• Published over sixty papers on most aspects of Theoretical Computer Science; lectured regularly at symposia and Computer Science departments since 1967.
• Received numerous NSF and/or DARPA grants in Theoretical Computer Science.
• Supervised twenty-six completed Ph.D.'s who now serve on tenured faculties at over a dozen leading universities, also at IBM, Bell and Lucent research labs.
• Editor-in-Chief, Information and Computation (An International Journal of Theoretical Computer Science); also served on editorial boards of MIT Press, numerous journals and handbooks of Theoretical Computer Science.
• Member or Chair of program committees and organizing committees for numerous symposia and workshops sponsored by ACM, IEEE, EATCS, AMS, ASL, NSF, SDC, IBM, INRIA, CSSR, USSR, Japan Info. Processing Soc.
• Previously served as: Chair, MIT Committee on Curricula (2003-2005), Chair, MIT Computer Science Graduate Program; Head, MIT Lab. for Computer Science Theory group; Associate Director, MIT Lab. for Computer Science.
• Appointed ACM Fellow November, 1999; elected to American Academy of Arts and Sciences, May, 1987; member of ACM, SIAM, MAA, ASL, IEEE.
• Consultant for GTE Internetworking, Hitachi America Ltd., GTE, Mitre Corp., NRC, IBM.

Education

Selected Publications

Books

1. Ito, T., and A.R. Meyer, eds., Theoretical Aspects of Computer Software, Proceedings of an International Symposium, Springer-Verlag, Lecture Notes in Comp. Sci. 526, September, 1991.
2. Meyer, A.R., J. Guttag, R. Rivest, and P. Szolovits, eds., Research Directions in Computer Science: An MIT Perspective, MIT Press, Cambridge Mass., 1991, 490pp.
3. Meyer, A.R. and M.A. Taitslin, eds., Logic at Botic,'89: Proceedings of a Symposium on Logical Foundations of Computer Science, Springer-Verlag, Lecture Notes in Comp. Sci. 363, July, 1989.

Articles

1. Stockmeyer, L.J. and A.R. Meyer, ``Cosmological Lower Bounds on the Circuit Complexity of a Small Problem in Logic'' (pdf), J. ACM 49, 6 (Nov. 2002), 753-784.
2. Jim, T. and A.R. Meyer, ``Full Abstraction and the Context Lemma (ps),'' SIAM J. Computation 25, 3 (1996), 663-696.
3. Jategaonkar, L. and A.R. Meyer, ``Deciding True Concurrency Equivalences on Finite Safe Nets,'' Theoretical Computer Science 154 (Jan. 1996), 107-143.
4. Seiferas, J.I. and A.R. Meyer, ``Characterization of Realizable Space Complexities,'' Ann. Pure and Applied Logic 73 (1995), 171-190.
5. Bloom, B., S. Istrail, and A.R. Meyer, ``Bisimulation Can't Be Traced,'' J. ACM 42, 1 (1995), 232-268.
6. Bloom, B. and A.R. Meyer, ``Experimenting with Process Equivalence'' (pdf), Theoretical Computer Science 101(2) (1992), 223--237.
7. Bruce, K.B., A.R. Meyer and J.C. Mitchell, ``The Semantics of Second-Order Lambda Calculus,'' Information and Computation, 85 (1990), 76-134. Reprinted in: Gerard Huet, editor. Logical Foundations of Functional Programming, chapter 10, pages 213-272. University of Texas at Austin Year of Programming Series. Addison-Wesley Publishing Company, 1990.
8. Meyer, A.R. "Puzzles in Programming Logic (pdf)," unpublished (1986)
9. Meyer, A.R. and M.B. Reinhold, `` `Type' is Not a Type,'' 13th ACM Symp. POPL (Jan., 1986), 287--295.
10. Meyer, A.R., ``What is a Model of the Lambda Calculus?'', Information and Control 52,1 (1982), 87-122.
11. Mayr, E. and A.R. Meyer, ``The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals,'' Advances in Mathematics 46,3 (1982), 305-329.
12. Mayr, E. and A.R. Meyer, ``The Complexity of the Finite Containment Problem for Petri Nets,'' J. ACM 28, 3 (July, 1981), 561-576.
13. Seiferas, J., M.J. Fischer and A.R. Meyer, ``Separating Nondeterministic Time Complexity Classes'' J. ACM 25,l (1978), 146--167.
14. Meyer, A.R., `` Weak Monadic Second Order Theory of Successor is not Elementary-Recursive (pdf),'' Logic Colloquium, Lecture Notes in Mathematics 453, Springer-Verlag, N.Y., (1975), 132--154.
15. Meyer, A.R., ``The Inherent Computational Complexity of Theories of Ordered Sets (tif),'' in Proc. Int'l. Cong. of Mathematicians, August 21--29, 1974, vol. 2, 477--482.
16. Stockmeyer, L. and A.R. Meyer, ``Word Problems Requiring Exponential Time'' (pdf), 5th ACM Symp. on Theory of Computing, (May, 1973), 1-10.
17. Meyer, A.R. and L. Stockmeyer, ``The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space'' (pdf), 13th IEEE Symp. on Switching and Automata Theory, (Oct., 1972), 125-129.
18. Meyer, A.R., ``Program Size in Restricted Programming Languages,'' Information and Control 2l, 4 (1972), 382-394.
19. Meyer, A.R. and M.J. Fischer, ``Economy of Description by Automata, Grammars, and Formal Systems'' (pdf, 4M), 12th IEEE Symp. on Switching and Automata Theory, (1971), 188--191.
20. McCreight, E.M., and A.R. Meyer, ``Classes of Computable Functions Defined by Bounds on Computation (pdf) ,'' 1st ACM Symp. Theory of Computing, (May, 1969), 79--88.
21. Meyer, A.R. and C. Thompson, ``Remarks on Algebraic Decomposition of Automata,'' Mathematical Systems Theory 3, 2 (1969), 110--118.
22. Meyer, A.R. and D.M. Ritchie, ``The Complexity of Loop Programs, (pdf)'' Proc. 22nd National ACM Conf., Thompson, Washington, D.C., (Aug., 1967), 465--470. (Awarded prize for best paper.)

Courses Taught

• 6.042J/18.400J, Mathematics for Computer Science
  • Spring '08 6.042 Notes and Spring '07 slide handouts (9M, 200pp pdf) are publicly available.
    (The Spring 08 Problems & solutions as well as the Spring '08 powerpoint slides sources are available to instructors on request to
           meyer (at) csail.mit.edu.)

  • Spring 08 6.042 Online Tutor

    is also available for public use:
    Register to get a Spring '08 Online Tutor password, then

    Log into the Tutor:

    User Name: Password: Prior term 6.042 material: many of the following course websites are password restricted; for access, email        meyer (at) csail.mit.edu. Spring '08, Fall '07, Spring '07, Fall '05, Spring '04, Fall '03, Fall'02, Spring '02, Fall '01, Fall '99, Spring '99, Spring '98. 6.844, Computability Theory Of and With Scheme, Spring '05 Spring '03; Earlier, undergraduate version: 6.044J/18.423J, Computability, Programming, and Logic, Fall '00, Fall '98, Fall '96. 6.045J/18.400J, Automata, Computability, and Complexity, Spring '01. 6.001, Structure and Interpretation of Computer Programs, Spring '00 (Recitation Handouts), Fall '97 (co-in-charge), Fall '96, Spring '95 (co-in-charge) Copyright © 2007, Albert R. Meyer. All rights reserved. This document last modified Monday, 19-Jan-2009 18:51:59 EST