When I joined DEC in 1985, they were the world leader in networking. Using their VMS operating system, I could type a simple copy command to a computer in California, specifying a file and machine name, to copy a file from a computer in Massachusetts.…
The purpose of this paper is to draw attention to existential fixed-point logic (EFPL). Among other things, we show the following. If a structure A satisfies an EFPL formula φ then A has a finite subset F such that every structure that coincides with A…
This article examines the direction in which knowledge bases are constructed for diagnosis and decision making When building an expert system, it is traditional to elicit knowledge from an expert in the direction in which the knowledge is to be applied, namely, from observable evidence…
Agora is an environment that supports the construction of large, evolutionary programs that manipulate complex data structures, e.g., problem solving systems. Agora can be customized to support the computational model that is most suitable for a given application. Agora has been designed explicitly to support…
Let G(n,p) be a random graph with n vertices and the edge probability p. We give an algorithm for Hamiltonian Path Problem whose expected run-time on G(n,p) is cn/p + o(n) for any fixed p. This is the best possible result for the case of…
I have only a vague memory of this paper. I believe Bhargava asked me to write a chapter about the results in [41] and [46]. I was probably too lazy and asked Dolev to write a chapter that combined his more recent results on connectivity…
We present a representation of partial confidence in belief and preference that is consistent with the tenets of decision-theory. The fundamental insight underlying the representation is that if a person is not completely confident in a probability or utility assessment, additional modeling of the assessment…
An approach to ray tracing complex models containing mathematically defined surfaces is presented. Parametric and implicit surfaces, and boolean combinations of these, are first tessellated into triangles. The resulting triangles from many such surfaces are organized in a hierachy of lists and 3D grids, allowing…
Richard Palais ran a column on mathematical typesetting in the AMS Notices, and he invited me to be guest columnist. This is what I wrote--a short exposition of my ideas about producing mathematical documents.
Performance analysis of a tactile sensor.
This message is the source of the following observation, which has been quoted (and misquoted) rather widely: A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable.
A number of famous theorems about first-order logic were disproved in [60] in the case of finite structures, but Lyndon's theorem on monotone vs. positive resisted the attack. It is defeated here. The counter-example gives a uniform sequence of constant-depth polynomial-size (functionally) monotone boolean circuits…
