In 1947, Post showed the word problem for semigroups to be undecidable. In 1950, Turing strengthened this result to cancellation semigroups, i.e. semigroups satisfying the cancellation property (1) if xy = xz or yx = zx then y = z. No semigroups with zero satisfies…
Let r be a Cohen real over a model V of ZFC; then the second-order V[r]-theory of the integers (even the reals if V satisfies CH) is interpretable in the monadic V-theory of the real line. Contrast this with the result of 79.
Current-controlled filters and euqalizers that employ operational transconductance amplifiers (OTAs) and capacitors are presented. Those circuits can be integrated in bipolar technology and are characterized by good linearity between controlled parameteres and their respective control currents.
We consider the questions whether polynomial time solutions for the easier problems of the list for 55 yield NP solutions for the harder ones, or vice versa. We show that affirmative answers to several of these questions are equivalent to natural principles like NP =…
I felt that in [40], I had presented the right way to do assertional (also known as Owicki-Gries style) reasoning about concurrent programs. However, many people were (and perhaps still are) hung up on the individual details of different programming languages and are unable to…
The genesis of this paper was my realization that, in a multiprocess system with synchronized clocks, the absence of a message can carry information. I was fascinated by the idea that a process could communicating zillions of bits of information by not sending messages. The…
We present an extension of first-order logic that captures precisely the computational complexity of (the uniform sequences of) constant-depth polynomial-time circuits.
Grapevine is a distributed, replicated system that provides message delivery, naming, authentication, resource location, and access control services in an internet of computers. The system, described in a previous paper [1], was designed and implemented several years ago. We now have had operational experience with…
Remote procedure calls (RPC) appear to be a useful paradigm for providing communication across a network between programs written in a high-level language. This paper describes a package providing a remote procedure call facility, the options that face the designer of such a package, and…
Functional languages supporting lazy evaluation invite novel applications, where conventional languages do not provide appropriate support for the problem. In this paper we present an application of functional languages to arbitrary precision real arithmetic, using an unusual technique based on continued fractions, and depending crucially…
PATHFINDER is a developing expert system to assist pathologists in the interpretation of findings noted on microscopic examination of lymph node tissue. We describe PATHFINDER's hypothesis-directed reasoning approach with an emphasis on intelligent question selection strategies, techniques for managing data inaccuracy, and explanation methods for…
Using a model tokamak equilibrium, the influence of a magnetic separatrix on the stability of the plasma against ideal MHD ballooning modes is investigated. It is found that there is no significant stabilizing effect from the strong global shear near the separatrix, but rather that…
