Reasoning about concurrent systems is simpler if they have fewer separate atomic actions. To simplify reasoning about systems, we'd like to be able to combine multiple small atomic actions into a single large one. This process is called reduction. This paper contains a reduction theorem…
There are simple algorithms with large outputs; it is misleading to measure the time complexity of such algorithms in terms of inputs only. In this connection, we introduce the class PIO of functions computable in time polynomial in the maximum of the size of input…
Yuri Matijasevich, famous for completing the solution of Hilbert's tenth problem, suggested to use differential equations inspired by real phenomena in nature, to solve the satisfiability problem for boolean formulas. The initial conditions are chosen at random and it is expected that, in the case…
The interpretation method is the main tool in proving negative results related logical theories. We examine the strength of the interpretation method and find a serious limitation. In one of our previous papers 57, we were able to reduce true arithmetic to the monadic theory…
The notion of linear time is very sensitive to machine model. In this connection we introduce and study class NLT of functions computable in nearly linear time n(log n)O(1) on random access computers or any other "reasonable" machine model (with the standard multitape Turing machine…
Lapped Orthogonal Transform (LOT) is a new tool for block transform coding with basis functions that overlap adjacent blocks. The LOT can reduce the blocking effect to very low levels. In this paper, an exact derivation of an optimal LOT is presented. The optimal LOT…
One of the most attractive features of functional programming languages is their suitability for programming parallel computers. This paper is devoted to discussion of such a claim. Firstly, parallel functional programming is discussed from the programmer's point of view. Secondly, since most parallel functional language…
Roughly fifteen years ago, Huet developed a complete semidecision algorithm for unification in the simply typed lambda-calculus (lambda). In spite of the undecidability of this problem, his algorithm is quite usable in practice. Since then, many imortant applications have come about in such areas as…
Growing enthusiasm about the application of autonomous reasoning in high-stakes domains like medicine and aerospace has stimulated interest in systems that behave in accordance with a coherent theory of rationality. Within such domains, the losses associated with suboptimal decisions tend to render simple satisfying approaches…
No abstract available.
We show that in a thermonuclear plasma the magnetosonic wave propagating normal to the magnetic field can be unstable. The growth rate is small, however, and the wave is easily stabilized by perpendicular thermal conduction.
This paper provides an introduction to writing concurrent programs with “threads”. A threads facility allows you to write programs with multiple simultaneous points of execution, synchronizing through shared memory. The paper describes the basic thread and synchronization primitives, then for each primitive provides a tutorial…
