Steven Lindell
Job Title: Professor of Computer Science

My Picture

Institution: Haverford College
Street address: 370 Lancaster Ave., Haverford, PA 19041
Office: Koshland L308, INSC
Office phone: (610) 896-1203 FAX number: (610) 896-4904
Email address:

My Schedule (Fall 2013)
Activity Time Location
CS 235
Information & Coding theory
MWF 10:30-11:30 S412
CS 399
Senior seminar
M 7:30-10:00 L309
Office hours MWF 11:30 L308

Events (recent and upcoming)

Date Location Presentation
September 20, 2013 HIGHLIGHTS of Logic, Games and Automata 2013
Paris, France
Presentation-invariant definability
ABSTRACT: We extend the notion of invariant elementary definability to a variety of different graph representations, including those that strictly extend the power of first-order logic with an arbitrary linear order.
October 26, 2012 AALAC/Mellon 23 Working Group on Information at Bryn Mawr College
Co-Sponsored by the NSF Center for Science of Information
Information: basic definitions
May 14, 2012 Finite and Algorithmic Model Theory 2012
École de Physique des Houches
Infinitary methods in finite model theory
March 30, 2012 Logical Approaches to Barriers in Complexity II
Isaac Newton Institute for Mathematical Sciences
Infinitary methods in finite model theory
Handout; Notes

I was featured in Haverford's newsletter, April 2006.


Teaching assistants

(* = NSF Graduate Fellowship recipient)

Rose Abernathy A history of mechanical thought Fall 2012
Lili Dworkin * A history of mechanical thought Fall 2010
Sam Wood * Analysis of algorithms Spring 2011

Summer research assistants

(* = NSF Graduate Fellowship recipient)

Gavriella Fried and
Jon Sweitzer-Lamme
A course resource for CS147:
The History of Mechanized Thought
Rose Abernathy Visualization of switching circuits for
formulas of first-order logic
Rebecca Knowles * Displaying formulas and data structures
for first-order logic over finite domains
Lili Dworkin * Labs to support the History of Computing 2009
Abby Novick Comparing college literacy and numeracy 2009
Anne Miller Linear-time algorithms for transitive closure 2008
Stephanie Hilton Graphical programming of data structures 2008
Michael Jablin Pen tablet technology in education 2006
Pat Clancy Mathematical typesetting by voice 2005

Senior thesis students

(* = NSF Graduate Fellowship recipient)

Year Name Topic Second major
2013 Chang Cao Complexity of Counting Mathematics
2012 Tanvi Surti Social Recommender Systems  
2011 Lili Dworkin * Automata-Theoretic Model Checking Mathematics
2011 Andrew Gonczi Fast distance queries in series-parallel graphs  
2009 Joe Huttner Recommendation algorithms using the SVD Spanish
2008 Alex Moser Digital Watermarking and DRM Sociology
2008 Anne Miller Linear-time algorithms for transitive closure Math (BMC)
2005 Lee Weinstein Scale-free networks and Random Graphs Mathematics
2004 Brian Bejile Bi-level Lossless Compression Techniques Economics
2002 Aaron Block * Quantum Computation: An Introduction Mathematics
2001 Todd Miller Kolmogorov Complexity  
2000 David Costello Computerized pricing of derivatives  
2000 Betsy Renner Human-Computer Interaction  
1998 Adam Schran Relational database design  
1997 Jeremy Manson Rewrite systems: Church-Rosser property  
1996 Nik Swoboda A Multivalued approach to default reasoning  
1993 Jon Hurwitz Introduction to digital image processing  
1993 Waimar Tun Gödel's (in)completeness theorems  
1993 Oolan Zimmer Alternation complexity and the BFVP Mathematics
1992 Mark Belasco A brief introduction to coding theory Mathematics
1990 Bryant Tolles A brief introduction to information theory Mathematics
1989 Hank Fieglein Parallel algorithms Mathematics
1988 Allen Gunn The Lambda calculus Mathematics


Biographical Information

I received my B.A. and M.A. in Mathematics at UCLA, and went on to receive a Ph.D. in theoretical Computer Science at UCLA under the supervision of Sheila Greibach and Yiannis Moschovakis (mathematical logic) in 1987. Since then I have been a member of the Computer Science program at Haverford College, which offers a major or minor, along with a concentration for Mathematics and Physics majors. The courses we offer are geared toward preparing students for graduate study by emphasizing the foundations of the subject.

My Teaching

(click for syllabus)

Course title

(click for course materials)

Brief description Other
Fluency with Information Technology A basic introduction to a wide range of computing and the technology behind it. satisfies "Q" requirement
Foundations of Rigorous Thinking Quantitative seminar which covers the logical foundations of human reasoning.. satisfies "Q" requirement
History of Mechanical Thought Writing seminar which covers the long and colorful history of computing, ancient and modern. satisfies freshman writing
Number Systems and Computer Arithmetic Advanced algorithms and circuit techniques for high speed arithmetic. intermediate level
CS/Math elective
Information and Coding Theory Shannon's classical theory of mathematical communication. intermediate level
CS/Math elective
Analysis of Algorithms An advanced theoretical course on the design of algorithms. core major requirement, cross-listed in Math
Theory of Computation An advanced course covering theoretical models and languages. core major requirement, cross-listed in Math
  • 393
Physics of Computation An advanced seminar which explains the deep connection between thermodynamics and energy efficient computation. CS elective


Back to Contents

My Research
I work on the foundations of theoretical computer science, in an area of logic known as finite model theory and the related field of descriptive complexity. I study the logical definability of complexity classes given by models of computation whose resources are bounded by mathematical (or physical) limits. My papers are often concerned with elementary (first-order) and inductive (fixed-point) definability on finite structures, in as much as these logics shed light on fundamental questions in the complexity of computation. More recently, I have been interested in logically characterizing the fundamental physical limitations of mechanical computing devices, and related general issues in the philosophical foundations of logic, information and computation. This work is highly abstract, but may be of substantial practical importance when it becomes impossible to make substantial technological improvements to computers.



  • "Real-Time Collaboration Tools for Digital Ink", Journal of Computing Sciences in Colleges, Volume 25, Number 3, January 2010, pp. 24-31.

  • "A normal form for first-order logic over doubly-linked data structures" IJFCS Vol. 19 No. 1 (Feb. 2008) pp. 205-217.

  • A Term Logic for Physically Realizable Models of Information (near final draft). Appears as Chapter 8 in the book The Old New Logic: Essays on the Philosophy of Fred Sommers published by MIT press (2005). ACM Computing Review
    Summary: A paper in two parts.  The first part establishes a mathematical model of information based on uniform arrangements of matter in space.  These so-called singulary structures correspond to material representations of symbolic patterns, determined by the physical requirements of storing arbitrarily large amounts of data in a memory of unbounded size.  The second part introduces a functionally based term logic using numerical threshold quantifiers without variables.  Our main result shows that this classically motivated singulary logic has the same expressive power as ordinary first-order logic within this context. It can be seen as contributing to the logical foundations of information.

Book Reviews


Talks (selected)

  • Logic and Models of Computation (lecture series given in the Third Indian School on Logic and its Applications on January 20-23, 2010 at University of Hyderabad, Gachibowli, India)
    1. History of logic
    2. Historical models of computation
    3. Computing without machines
    4. Logical definability over finite models
    5. First-order logic over doubly-linked data structures
  • "Real-Time Collaboration Tools for Digital Ink" (October 30, 2009 at Villanova University in the 25th Annual Consortium for Computing Sciences in Colleges Eastern Conference).
  • Computation: A Mathematical or Physical Notion? (November 5, 2007 at Villanova University) Abstract: Models of computation such as the Turing machine are based on the idealized psychological characteristics of a human calculator -- an autonomous machine that changes its "state of mind" in a stepwise fashion based on the recognition of symbolic cellular configurations. This leads to a mathematical model of effective computability, and its complexity is traditionally quantified by measuring the amount of time (steps) and space (cells) required in the computation. However, a concrete model of computation must use matter and energy, operating under natural constraints governed by the laws of physics. This leads to a new notion of feasibility based on physical resources, particularly when the laws of thermodynamics and gravitation are taken into account.
  • A physical analysis of mechanical computability (May 25, 2006 at the Isaac Newton Institute for Mathematical Sciences). Abstract: Turing's model of autonomous computation is based on the idealized psychological characteristics of a human calculator -- its ability to change its "state of mind" in a stepwise fashion based on the recognition of symbolic configurations. This leads to a mathematical model of effective computability, with its well known capabilities and limitations. We extend this analysis to the idealized physiological characteristics of a machine computer -- its ability to manipulate matter using energy. This leads to a new notion of feasibility based on physical resource bounds, in which mass and energy constraints further restrict the usual notions of space and time complexity.
  • A normal form for singulary logic over physically realizable data models (February 28, 2006 at the Isaac Newton Institute for Mathematical Sciences in Cambridge, England as part of the Logic and Databases Workshop). [audio] Summary: Relying on the symmetry of labeled connections between elements of the structure, this result shows that elementary definability can be reduced to boolean combinations of numerical quantifiers applied to quantifier-free formulas.
  • Computing monadic fixed-points in linear-time on doubly-linked data structures (June 24, 2005 at Seventh International workshop on Logic and Computational Complexity). Abstract: In general, the computational effort required solving a problem described by a first-order or fixed-point query (logical formula) requires time polynomial in the size of the database (finite structure). We show how a linear-time evaluation algorithm for first-order logic on bounded-degree data structures can be extended to monadic fixed-point formulas, pointing the way to a logical characterization of linear-time computability. Summary
  • Revisiting finite-visit computations (June 21, 2004 at rump session of Conference on Computational Complexity) Summary: Incorporating matter and energy requirements into physically implemented machines sheds new light on feasible computability. Under certain circumstances, conventional mathematical models may not be asymptotically realizable due to the limited availability of resources required to store data and execute instructions.
  • Linear-time algorithms for Monadic Logic (University of Pennsylvania's Logic and Computation Seminar, February 2003) [a shorter version skipping slides 7, 9, 10, 11 was given at the rump session of LICS 2003]. Summary: Descriptive complexity studies the asymptotic computational effort required to evaluate logical queries on finite databases, with a focus on queries expressed by first-order or fixed-point formulas. In general, these queries require a polynomial amount of time with respect to the size of the structure. We illustrate the special case of how monadic first-order formulas can be evaluated in linear-time on ordinary data structures. We even extend this to monadic fixed-point formulas, leading to the possibility of providing a logical characterization of linear-time computability.
  • Physically Scalable Computation - an axiomatic approach (June 19, 2001 at rump session of Conference on Computational Complexity) Summary: A consideration of the matter and energy requirements of physically implemented machines leads tentatively to a finer mathematical analysis of asymptotic space and time computability. 
  • Computer Science as a Liberal Art: the Convergence of Technology and Reason, (a Faculty Research talk presented at Haverford College on January 24, 2001). Summary: Aimed at a general non-mathematical audience, I hope to explain how logical reasoning can be used to understand the fundamental theoretical issues behind the future potentials and limits of computing technology. Included will be a discussion of how this study can be viewed as continuing in the historical tradition of the seven original liberal arts.
  • The Role of Decidability in First Order Separations over Classes of Finite Structures, given at the Logic in Computer Science conference in Santa Barbara, California June 2000. Abstract
  • Using non-standard techniques to analyze first-order definability over finite structures was an invited presentation at the NSF/DIMACS sponsored Workshop on Logic and Cognitive Science, given at the University of Pennsylvania's Institute for Research in Cognitive Science, April 18th, 1999.
  • Fixed-point versus first-order definability on structures with arithmetic, invited presentation at the DIMACS workshop on Descriptive Complexity and Finite Models, Princeton University, January 17, 1996.
  • A Constant-Space Model of Computation for First-Order Queries (presented at the DIMACS Special Year on Logic and Algorithms Seminar, November 8, 1995 and also at the University of Pennsylvania in their Logic and Computation seminar on Monday, April 3, 1995). Abstract
  • Computing Without Machines – a logical approach to the mathematics of computation, at the Haverford-Bryn Mawr mathematics colloquium on Friday, March 18, 1994.
  • A Logspace Algorithm for Tree Canonization (presented at the 1992 ACM Symposium on the Theory of Computing).
  • Fixed-point Logic and Cyclic Formulas -- Finite Model Theory and its Connections with Computational Complexity (VILLANOVA UNIVERSITY Computer Science Colloquium October 10, 1991). Abstract
  • The invariant problem for binary string structures and its connection with the parallel complexity of queries, (presented at the annual meeting of the Association for Symbolic Logic held in the University of California, Berkeley January 1990). Abstract
For a simple one page resume, click here.
Back to Contents

Other Interests (under development)

Keeping things in perspective: Before you think computers can solve the world's problems, think again. This article "The Poet and the Computer" by Norman Cousins is from the UCLA magazine, and is posted here with permission of the editors.
Recovering from RSI (Repetitive Strain Injury)
I have nearly recovered from a severe repetitive strain injury which had left me disabled in the spring of 1996. The purpose of this section will be to educate others in prevention, treatment, and adaptation. One thing to remember: computers don't injure you, you injure yourself in the course of operation.
Classical Education
Originally, there were seven liberal arts, divided into two sections.

Back to Contents
Last revised: September 14, 2013.