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.
|
Manuscripts
|
"A normal
form for first-order logic over doubly-linked
data structures" IJFCS to appear (see
also preprint manuscript)
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.
"Generalized
Implicit Definitions on Finite Structures"
(co-written with Stéphane Grumbach & Zoé
Lacroix), in Kleine-Büning, H. (ed.), Computer
Science Logic '95, Springer-Verlag,
Lecture Notes in Computer Science Vol. 1092,
1996, pp. 252-265.
"First
Order Logic, Fixed Point Logic and Linear Order"
(co-written with Anuj Dawar & Scott
Weinstein), in Kleine-Büning, H. (ed.), Computer
Science Logic '95, Springer-Verlag,
Lecture Notes in Computer Science Vol. 1092,
1996, pp. 161-177.
"A Constant-Space Sequential
Model of Computation for First-Order Logic" Logic
and Computational Complexity, Lecture
notes in Computer Science no. 960, Daniel Leivant
(ed.), Springer-Verlag 1995 pp. 447-462.
"Infinitary
Logic and Inductive Definability over Finite
Structures" (co-written with Anuj Dawar
& Scott Weinstein), Information and
Computation, Vol. 119, No. 2, June 1995
pp. 160-175.
"A Purely Logical
Characterization of Circuit Uniformity, " in
Proceedings of the 7th Annual IEEE
Conference on Structure in Complexity Theory,
(1992), pp. 185-192.
A Logspace
Algorithm for Tree Canonization in
Proceedings of the 24th Annual ACM
Symposium on the Theory of Computing
(1992), pp. 400-404.
"The Invariant Problem for
Binary String Structures and the Parallel
Complexity Theory of Queries," Journal
of Computer and System Sciences, Vol.
44, no. 3, June 1992, pp. 385-410.
"An Analysis of Fixed-Point
Queries on Binary Trees," Theoretical
Computer Science, Vol. 85 (1991) 75-95.
Book Reviews
Dissertation
|
Talks (selected)
- A
physical analysis of mechanical computability
(presented 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 (presented
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 (presented 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 (presented 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 (presented
at the 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
(presented 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.
- Nonstandard methods for Analyzing 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.
- Fixed-point Logic and Cyclic Formulas --
Finite Model Theory and its Connections with
Computational Complexity (VILLANOVA
UNIVERSITY Computer Science Colloquium October
10, 1991). Abstract
|