[CS Dept., U Chicago]


Michael J. O'Donnell (Mike)

Curriculum Vitae

A longer version is available in LaTeX, DVI, PostScript, PDF, and HTML forms. A short biography appears in Who's Who in America.

Education

Employment

Professional Societies and Honors

Phi Beta Kappa, Association for Computing Machinery, Association for Symbolic Logic, Computer Society of IEEE, Acoustical Society of America, American Physical Society, Computer Professionals for Social Responsibility, Free Software Foundation, Who's Who in America.

Research Interests

Consulting

Articles in Refereed Journals

  1. Geometrical problems with applications to hashing (with D. Comer). SIAM Journal on Computing, 11(2):217-226, May 1982. Also appeared as Purdue University Technical Report TR-303, 1979.
  2. Pattern matching in trees (with C. Hoffmann). Journal of the ACM, 29(1):68-95, January 1982. Also appeared in the collection Computer Algorithms: string pattern matching strategies, J.-I. Aoe, editor, IEEE Computer Society Press, Los Alamitos CA, 1994, 154-181.
  3. Programming with equations (with C. Hoffmann). ACM Transactions on Programming Languages and Systems, 4(1):83-112, January 1982. A preliminary version of 2 and 3, with some additional material, appeared as An interpreter generator using tree pattern matching. 6th Annual ACM Symposium on Principles of Programming Languages, 169-179, January 1979.
  4. A critique of the foundations of Hoare-style programming logics. Communications of the ACM, 25(12):927-934, December 1982. Also appeared as Purdue University Technical Report TR-338, 1980, and in the Logics of Programs Workshop, D. Kozen editor, Yorktown Heights, New York, May 1981, Lecture Notes in Computer Science, 131:349-374, Springer-Verlag, 1982.
  5. The expressiveness of simple and second order type structures (with S. Fortune and D. Leivant). Journal of the ACM, 30(1):151-185, January 1983. Also appeared as IBM Research Report RC 8542 (#37221) 10/31/80. Some of the material in this paper also appeared in conference 1 and lecture 1.
  6. A combinatorial problem concerning interconnection networks (with C. Smith). IEEE Transactions on Computing, C-31(2):163-164, February 1982. Also appeared as Purdue University Technical Report CSD TR 352, 1981.
  7. A combinatorial analysis of static-key hashing (with F. Berman, M. Bock, E. Dittert and D. Planck). SIAM Journal on Computing, 15(2):604-618, May 1986.
  8. Lower bounds for sorting with realistic instruction sets (with E. Dittert). IEEE Transactions on Computers, C-34(4):311-317, April 1985. Also appeared as Johns Hopkins University Technical Report JHU/EECS 84/06. An error is corrected in C-35(10):932, October 1986.
  9. Implementation of an interpreter for abstract equations (with C. Hoffmann and R. Strandh). Software -- Practice and Experience, 15(2):1185-1204, December 1985. An earlier version, by Hoffmann and O'Donnell, appeared in 10th Annual ACM Symposium on Principles of Programming Languages, 111-120, January 1984. Also appeared as Johns Hopkins University Technical Report JHU/EECS/84/03, 1984.
  10. How to prove representation-independent independence results. (with Stuart A. Kurtz and James S. Royer). Information Processing Letters, 24:5-10, January 1987. Also appeared as University of Chicago Department of Computer Science Technical Report 85-06, 1985.
  11. Some intuitions behind realizability semantics for constructive logic: Tableaux and Läuchli countermodels (with J. Lipton), Annals of Pure and Applied Logic, 81:187-239, 1996. Carries on the program presented in unrefereed 5.
  12. Leveled Garbage Collection (with G. Tong). Journal of Functional and Logic Programming 2001:5, July 2001.
  13. Cell-Utes and Flutter-Tongue Cats: Sound Morphing Using Loris and the Reassigned Bandwidth-Enhanced Model (with K. Fitz, L. Haken, S. Lefvert, C. Champion). Computer Music Journal 27(3):44-65, Fall 2003.
  14. A Proposal to Separate Handles from Names on the Internet. Communications of the Association for Computing Machinery, 48(12):78-83, December 2005. Longer version in Technical Reports [9].

Competitive Conference Papers

  1. A programming language theorem which is independent of Peano arithmetic. 11th Annual ACM Symposium on Theory of Computing, 176-186, May 1979. Similar papers appeared as A practical programming theorem which is independent of Peano arithmetic. 100th Anniversary Conference in honor of Gottlob Frege, Friedrich Schiller Universität, Jena, D.D.R., 1979, and as Purdue University Technical Report TR-299, 1979.
  2. Parallel stepwise simulation of combinatory reduction systems. 1984 Conference on Information Sciences and Systems, Princeton, N.J., May 1984. A longer version containing additional material appeared as Universal reduction systems for sequential and parallel computation, Johns Hopkins University Technical Report JHU/EECS/84/04, 1984, and was included in book 3.
  3. Realizability semantics for error-tolerant logics (with J. Mitchell). In J. Halpern, editor, Theoretical Aspects of Reasoning About Knowledge, Proceedings of the 1986 Conference, Morgan Kaufman, New York, 1986. An earlier version by O'Donnell appeared as A type-theoretic foundation for epistemic and relevance logics, Johns Hopkins University Technical Report JHU/EECS/85/02.
  4. Exact real arithmetic: a case study in higher order programming (with H-J. Boehm, R. Cartwright, and M. Riggle). 1987 Symposium on LISP and Functional Programming.
  5. Testing confluence of nonterminating overlapping systems of rewrite rules (with Y. Chen). Conditional and Typed Rewriting Systems, 2nd International CTRS Workshop, Montreal, June 1990. Lecture Notes in Computer Science 516, Springer-Verlag, 1991, pp. 127-136. Preliminary versions appeared as University of Chicago Department of Computer Science Technical Report 89-03, 1989 and 90-07, 1990.
  6. Infinite Terms and Infinite Rewritings (with Y. Chen). Conditional and Typed Rewriting Systems, 2nd International CTRS Workshop, Montreal, June 1990. Lecture Notes in Computer Science 516, Springer-Verlag, 1991, pp. 115-126. Preliminary version appeared as University of Chicago Department of Computer Science Technical Report 90-08, 1990.
  7. Sound Morphing using Loris and the Reassigned Bandwdith-Enhanced Additive Sound Model: Practice and Applications (with S. Lefvert, K. Fitz, L. Haken). International Computer Music Conference, Göteborg, 16-21 September 2002.

Book Chapters

  1. Introduction: Logic and Logic Programming Languages. Chapter 1 of Handbook of Logic in Artificial Intelligence and Logic Programming, volume 5 on Logic Programming, D. Gabbay editor, Oxford University Press, 1998, pp. 1-67. Preprint as University of Chicago Department of Computer Science Technical Report 94-15 , October 1994.
  2. Equational Logic Programming. Chapter 2 of Handbook of Logic in Artificial Intelligence and Logic Programming, volume 5 on Logic Programming, D. Gabbay editor, Oxford University Press, 1998, pp. 69-161. Preprint as University of Chicago Department of Computer Science Technical Report 94-16 , October 1994.

Unrefereed Papers and Technical Reports

  1. Toward a fully parallel implementation of the lambda calculus (with R. Strandh). Johns Hopkins University Technical Report JHU/EECS/84/13, 1984. Not published because of uncorrectable errors.
  2. Multidimensional interpolation at inaccurate points (with E. Dittert). Johns Hopkins University Technical Report JHU/EECS/84/17, 1984.
  3. Proving unorientable equational formulas (with Y. Chen). University of Chicago Department of Computer Science Technical Report 90-26, August 1990.
  4. Nonterminating rewritings with head boundedness (with Y. Chen). University of Chicago Department of Computer Science Technical Report 90-27, August 1990. Submitted for journal publication.
  5. Connecting formal semantics to constructive intuitions (with S. Kurtz, J. Mitchell). Proceedings of a Symposium on Constructivity in Computer Science, Trinity University, San Antonio TX, June 1991. Lecture Notes in Computer Science, J. P. Myers and M. J. O'Donnell editors, Volume 613, Springer-Verlag, 1992, pp. 1-21. Also appeared as University of Chicago Department of Computer Science Technical Report 92-01, January 1992. Also presented at the annual meeting of the Association for Symbolic Logic, Notre Dame, February 1993.
  6. Decomposition of steady state instrument data into an excitation system and a formant filter components (with I. Bisnovatyi). COST Digital Audio Effects Workshop, DAFx99, Trondheim, Norway, 9-11 December 1999.
  7. The sound manifesto (with I. Bisnovatyi). Critical Technologies for the Future of Computing, at a meeting of The International Society for Optical Engineering (SPIE), San Diego, CA, 30 July through 4 August 2000.
  8. Open Network Handles Implemented in DNS. Internet Draft draft-odonnell-onhs-imp-dns-00.txt filed with Internet Engineering Task Force, 17 September 2002. The same text, with different pagination, is archived in CoRR as cs.NI/0301011, 14 January 2003.
  9. A Proposal to Separate Handles from Names on the Internet. CoRR report cs.NI/0302017, 12 February 2003. Shorter version in Refereed [14].

In Preparation and Submitted

  1. Against Nonmonotonic Logic.
  2. Relational realizability (with J. Lipton).

Books

  1. Computing in Systems Described by Equations, Lecture Notes in Computer Science, Volume 58, Springer-Verlag, 1977. A preliminary version appeared as Subtree replacement systems: a unifying theory for recursive equations, LISP, Lucid and combinatory logic. 9th Annual ACM Symposium on Theory of Computing, 295-305, May 1977. Also appeared as Reduction Strategies in Subtree Replacement Systems, Ph.D. Dissertation, Cornell University, August 1976.
  2. A Programming Logic (with R. Constable), Winthrop, 1978.
  3. Equational Logic as a Programming Language, MIT Press, 1985. Includes some material from papers 2, 3, 9 and conference 2, as well as original material.

Invited Lectures

  1. Computational complexity and proof-theoretic power in typed lambda calculi. American Mathematical Society Summer Meeting, 1982. Abstract appeared in Abstracts of the American Mathematical Society, 3(5):376, August 1982. Results from paper 5.
  2. Two lectures on logic and computer science: 1. Does arrow denote implication or functionality? A profound mathematical pun. 2. Why the Church-Turing thesis doesn't help parallel functional programming. University of Maryland Special Year in Mathematical Logic and Theoretical Computer Science, October 1984. Results from paper 5, book 3, and original material.
  3. What it means to have a universal parallel reduction language. Graph Reduction Workshop, Santa Fe, October 1986. Results from book 3.
  4. Survey of the equational logic programming project. Colloquium on Resolution of Equations in Algebraic Structures, Lakeway, Texas, March 1987. Survey of material from papers 3, 9, book 3, plus original material. Also appeared as University of Chicago Department of Computer Science Technical Report 87-04 , March 1987.
  5. Term-rewriting implementation of equational logic programming. In P. Lescanne, editor, Rewriting Techniques and Applications, Bordeaux, France, May 1987, Proceedings, Lecture Notes in Computer Science, 256, Springer-Verlag, 1987. Similar material to invited lecture 4. Also appeared as University of Chicago Department of Computer Science Technical Report 87-03, March 1987.
  6. Open Problems in Equational Logic Programming. Distinguished Lecture Series, SUNY Stony Brook, February 1988. Similar material to invited lectures 4, 5.
  7. Equational Logic as a Programming Language. Colloquium Series in Term Rewriting, Portland State University, March 1991. Similar material to invited lectures 4, 5, 6.
  8. Electronic Journals--scholarly invariants in a changing medium. Conference on Academic and Professional Journals in the Twentieth Century, University of Chicago, April 1992 (presented by author as discussant for session on "The Future of Journals"). Also appeared (unrefereed) in Journal of Scholarly Publishing, v. 26, no. 3, April 1995, University of Toronto Press, pp. 183-199, and as University of Chicago Department of Computer Science Technical Report 92-07, April 1992.
  9. Issues Involved in Publishing an Electronic Journal. Seminars on Academic Computing 1993 University Executive Program, Snowmass CO, August 1993. Very similar to lecture 8, but a more detailed presentation. Revised version of paper appeared as University of Chicago Department of Computer Science Technical Report 93-11, July 1993.
  10. Intuitive Counterexamples for Constructive Fallacies (with J. Lipton). Mathematical Foundations of Computer Science 1994 - 19th Annual Symposium, MFCS '94, Kosice, Slovakia, August 1994 - Proceedings, Igor Prívara, Branislav Rovan and Peter Ruzicka editors, Springer-Verlag, 1994, pp. 87-111. Also appeared as University of Chicago Department of Computer Science Technical Report 94-17, October 1994.
  11. The Structure of Scholarship in Cyberspace. Professors and Publishing in the Electronic Academy, the University of Tennessee, Knoxville Library, September 1996.
  12. The Sources of Certainty in Computation and Formal Systems. Computer Science as a Human Science: The Cultural Impact of Computerization, the 1999--2000 Sawyer Seminar at the University of Chicago. The University of Chicago, October 1999.
  13. Against Nonmonotonic Logic. ACM SIGART Chicago, March 2001.

Software Research Projects

  1. Equation Interpreter/Compiler (with C. Hoffmann, G. Sacco, P. Golick, R. Strandh, S. Rebelsky, D. Sherman, S. Bailey). Announced in SIGPLAN Notices, September 1983. Demonstrated at the Workshop on Logics of Programs, 1985. Abstract appeared as ``Equational logic as a programming language'', Logics of Programs: Proceedings 1985, Lecture Notes in Computer Science 193:255, Springer-Verlag, 1985. First distribution May, 1983. Second distribution as compiler December, 1985. Further versions in Ph.D. dissertations. Distributed to more than 45 sites worldwide.
  2. CJStruct, LaTeX macros for the Chicago Journal of Theoretical Computer Science. cjstruct.sty allows unamiguous structural markup of published journal articles in LaTeX source format. First version distributed 4 April 1995. Used by MIT Press for CJTCS and for the Journal of Functional and Logic Programming.

Editorial Duties

Professional Service (selections)

Undergraduate Courses

Graduate Courses

College Student Research

at U. Chicago

  1. Gerald Penn, 1988-89: computational linguistics.
  2. Michael Wolraich, 1992-93: compiling lazy functional programs.
  3. Terrence Asselin, Marc Dreyfuss, William Reardon, 1994-95: functional implementation of chunky lists.
  4. Mazin As-Sanie, 1995: digital sound synthesis.
  5. David Kearns, 1995: mathematical music theory.

Mr. Penn, Wolraich, Asselin, Dreyfuss, and Reardon were supported by National Science Foundation grants under the Research Experience for Undergraduates program.

at U. Iowa

  1. Michael Callahan, 1997: Java implementation of a tool for segmenting sound files.
  2. Isabel O'Meara, 1997: spectral analysis of recorded orchestral instruments.

Mr. Callahan and Ms. O'Meara were supported by a National Science Foundation site grant to U. Iowa under the Research Experience for Undergraduates Program.

M.S. Students

The University of Chicago

  1. Susanne Lefvert, 2001-2002, user interface for Loris sound analysis/morphing/synthesis software.

Ph.D. Students

Purdue University

  1. Paul Chew, 1979-1981, Normal Forms in Term Rewriting Systems.
  2. Eric Dittert, 1980-1982, On the Complexity of Retrieving Information.

The Johns Hopkins University

  1. Robert Strandh, 1983-1987, Compiling Equational Programs into Efficient Machine Code.

The University of Chicago

  1. Samuel Rebelsky, 1987-1993, Tours, a System for Lazy Term-Based Communication.
  2. David Sherman, 1987-1994, Run-Time and Compile-Time Improvements to Equational Programs.
  3. Donald Ziff, 1989-1995, Lazy Functional Programming for Full-Text Information Retrieval.
  4. Stephen Bailey, 1988-1995, Hielp, a Fast Interactive Lazy Functional Language System.
  5. Guanshan Tong, 1993-1998, Design and Evaluation of a High-Performance Automatic Memory Management System.
  6. Ilia Bisnovatyi, 1993-present, sound synthesis.

Postdoctoral Associates

  1. William Winsborough, 1988-90.
  2. Yiyun Chen, 1989-91.

Copyright Michael J. O'Donnell <michael_odonnell@acm.org>.
Licensed for free use.

 Valid HTML 4.0!

This page is generated from PHP source code, with supporting files.



Last modified: Mon Dec 5 19:15:06 CST 2005