#  Publications: Technical Articles, Theses, and Reports 

 



1. Two applications of hand-printed two-dimensional computer input; A.B. Thesis, Harvard University, Cambridge, Massachusetts, 1968
2. SHAPESHIFTER: An interactive program for experimenting with com\\-plex-plane transformations; Proceedings of the 23rd National Conference of the Association for Computing Machinery, 1968; pp. 717--724
3. An interactive graphics facility under the PDP-10/50 timesharing monitor; Proceedings of the DECUS Fall 1969 Conference; pp. 59--62
4. Techniques for generating, manipulating, and storage management of type 340 display files; Proceedings of the DECUS Fall 1969 Conference; pp. 67--74
5. (with Malcolm C. Bruce) A device to make a Rand tablet act like a light pen; Proceedings of the DECUS Spring 1970 Conference; pp. 249--251
6. (with Warren D. Goldfarb) The decision problem for formulas with a small number of atomic subformulas; Journal of Symbolic Logic, 38 (1973); pp.471--480
7. Stal O. Aanderaa and Harry R. Lewis, Prefix classes of Krom formulas; Journal of Symbolic Logic, 38 (1973); pp. 628--642
8. Herbrand Expansions and Reductions of the Decision Problem; Ph.D. Thesis, Division of Engineering and Applied Physics, Harvard University, 1974
9. Stal O. Aanderaa and Harry R. Lewis, Linear sampling and the AEA case of the decision problem; Journal of Symbolic Logic, 39 (1974); pp. 519--548
10. Program schemata and the first-order decision problem; Journal of Computer and Systems Sciences, 8 (1974); pp. 71--83
11. Description of restricted automata by first-order formulae; Mathematical Systems Theory, 9 (1975); pp. 97--104
12. Warren D. Goldfarb and Harry R. Lewis, Skolem reduction classes; Journal of Symbolic Logic, 40 (1975); pp. 62--68
13. Krom formulas with one dyadic predicate letter; Journal of Symbolic Logic, 41 (1976); pp. 341--362
14. Renaming a set of clauses as a Horn set; Journal of the Association for Computing Machinery, 10 (1978); pp. 134--135
15. The equivalence problem for program schemata with nonintersecting loops; Proceedings of the Fourth Association for Computing Machinery Symposium on Principles of Programming Languages, 1977; pp. 253--266
16. Harry R. Lewis and John H. Reif, Symbolic evaluation and the global value graph; Proceedings of the Fourth Association for Computing Machinery Symposium on Principles of Programming Languages, 1977; pp. 102--118
17. Complexity measures for combinatorial decision problems of the tiling variety; Proceedings of the Conference on Theoretical Computer Science held at Waterloo, Ontario, August, 1977; pp. 62--73
18. A new decidable problem, with applications; Proceedings of the 18th Symposium on Foundations of Computer Science, 1977; pp.~62--73
19. Harry R. Lewis and Christos H. Papadimitriou, Efficient computability; Scientific American, 238 (1978); pp. 253--266
20. Henry H. Leitner and Harry R. Lewis, Why Johnny can't program; Proceedings of the SIGCSE/CSA Technical Symposium on Computer Science Education, SIGCSE Bulletin, 10, 1 (1978); pp. 266--276
21. William R. Franklin and Harry R. Lewis, 3-D display of discrete spatial data by prism maps; Computer Graphics, 12 (1978); pp. 70--75
22. Complexity of solvable cases of the decision problem for the predicate calculus; Proceedings of the Nineteenth IEEE Symposium on the Foundations of Computer Science, 1978; pp. 35--47
23. Review of *Mariages Stables* by Donald E. Knuth; SIGACT NEWS; Winter 1978
24. Satisfiability problems for propositional calculi; Mathematical Systems Theory, 13 (1979); pp. 45--54
25. Complexity results for classes of quantificational formulas; Journal of Computer and Systems Sciences, 21 (1980); pp. 317--353
26. Stal O. Aanderaa, Egon Borger, and Harry R. Lewis, Conservative reduction classes of Krom formulas; Journal of Symbolic Logic, 19 (1982); pp. 110-130
27. Harry R. Lewis and Christos H. Papadimitriou, Symmetric space-bounded computation, extended abstract; Proceedings of the 7th International Colloquium on Automata, Languages, and Programming; Springer-Verlag Lecture Notes in Computer Science, 85, pp. 374--384
28. Harry R. Lewis and Christos H. Papadimitriou, Symmetric space-bounded computation; Theoretical Computer Science 19 (1982); pp. 161--187
29. Ashok K. Chandra, Harry R. Lewis, and Johann Makowsky, Embedded implicational dependencies and their inference problem; Proceedings of 13th ACM Symposium on Theory of Computing, 1981; pp. 342--354
30. Larry Denenberg and Harry R. Lewis, A hard problem for NTIME(n^k); Proceedings of the 1981 Allerton Conference; August, 1981
31. Yuri Gurevich and Harry R. Lewisl, The inference problem for template dependencies, preliminary version; Proceedings of ACM SIGACT-SIGMOD Symposium on Principles of Database Systems; Los Angeles, 1982
32. Yuri Gurevich and Harry R. Lewis, The inference problem for template dependencies; Information and Control 55 (1982); pp. 69--79
33. Yuri Gurevich and Harry R. Lewis, The word problem for cancellation semigroups with zero; Journal of Symbolic Logic 49 (1984); pp. 184-191
34. Harry R. Lewis and Richard Statman, Unifiability is complete for co-NLog space; Information Processing Letters 15 (1982); pp. 220-222
35. Larry Denenberg and Harry R. Lewis, The complexity of the satisfiability problem for Krom formulas; Theoretical Computer Science 30 (1984); pp. 319-341
36. Review of Garey and Johnson; *Computers and Intractability:* A Guide to the Theory of NP-Completeness, Journal of Symbolic Logic 48 (1983); pp. 498--500
37. Larry Denenberg and Harry R. Lewis, Logical syntax and computational complexity; Computation and Proof Theory: Proceedings, Logic Colloquium Aachen 1983, Part II; Springer-Verlag Lecture Notes in Mathematics 1104 (1983), pp. 101-115
38. Yuri Gurevich and Harry R. Lewis, A logic for constant-depth circuits; Information and Control 61 (1984); pp.65--74
39. Harry R. Lewis and John H. Reif, Efficient symbolic analysis of programs; Journal of Computer and Systems Sciences 32 (1986); pp. 280-314
40. Finite-state analysis of asynchronous circuits with bounded temporal uncertainty, TR-15-89; Harvard University, Center for Research in Computing Technology; 1989
41. A logic of concrete time intervals; IEEE Conference on Logic in Computer Science (1990); p. 380
42. Computing's Cranky Pioneer (review of I. Bernard Cohen's biography *Howard Aiken* and its companion volume *Makin' Numbers*); *Harvard Magazine*; May--June 1999
43. [Talented Eccentrics](http://www.harvardmagazine.com/2007/03/talented-eccentrics.html) (review of Scott Rosenberg's book, *Dreaming in Code*), Harvard Magazine, March-April 2007.
44. [Digital Books](http://ijh.cgpublisher.com/product/pub.26/prod.1664), *Inernational Journal of the Humanities,* Vol. 7, no. 8, pp. 59--66.
45. Renewing the Civic Mission of American Higher Education (with Ellen Condliffe Lagemann), in *What is College For? The Public Purpose of Higher Education,* Lagemann and Lewis, eds., Teachers College Press, 2011.
46. After the Digital Explosion: Education and Civil Liberties in the Internet Age, in *Teaching America,* Feith, ed., Rowman & Littlefield, 2011.
47. Protoball at Harvard: From Pastime to Contest,*Base Ball,* V. 5, no. 1 (Spring 2011), 41-45**.**
48. Renewing the civic mission of American higher education (with Ellen Condliffe Lagemann), in *What is Colelge For?*, Lagemann and Lewis, eds, Teachers College Press, 2011,pp. 9-45.
49. Lewis, Harry. [The Internet and Hieronymus Bosch: Fear, Protection, and Liberty in Cyberspace](/file_url/302), in Shephard, Kosslyn, and Hammonds, eds., The Harvard Sampler, Harvard University Press, 2011, pp. 57-90.
50. Lewis, Harry. After the Digital Explosion: Education and Civil Liberties in the Internet Age, in Feith, David, ed., Teaching America: The Case for Civic Education, Rowman & Littlefield, 2011, 183-192.