April 1988 - Vol. 31 No. 4
Features
Reasoning with worlds and truth maintenance in a knowledge-based programming environment
In traditional knowledge-based system development environments, the fundamental representational building blocks are mechanisms such as frames, rules, and attached procedures. The KEE system has been extended to include both a context (worlds) system and a truth maintenance system.
Undebuggability and cognitive science
A resource-realistic perspective suggests some indispensable features for a computer program that approximates all human mentality. The mind's program would differ fundamentally more from familiar types of software. These features seem to exclude reasonably establishing that a program correctly and completely models the mind.
Relational database design using an object-oriented methodology
Of the many approaches to relational database design, the Object Modeling Technique (OMT) is particularly effective. A comprehensive explanation and two applications show the semantic improvement of OMT over other approaches.
Cost/benefit analysis for incorporating human factors in the software lifecycle
New software engineering techniques and the necessity to improve the user interface in increasingly interactive software environments have led to a change in traditional software development methods. Methodologies for improvement of the interface design, an overview of the human factors element, and cost/benefit aspects are explored.
Computing Poisson probabilities
We propose an algorithm to compute the set of individual (nonnegligible) Poisson probabilities, rigorously bound truncation error, and guarantee no overflow or underflow. Work and space requirements are modest, both proportional to the square root of the Poisson parameter. Our algorithm appears numerically stable. We know no other algorithm with all these (good) features. Our algorithm speeds generation of truncated Poisson variates and the computation of expected terminal reward in continuous-time, uniformizable Markov chains. More generally, our algorithm can be used to evaluate formulas involving Poisson probabilities.
Linear hashing and spiral storage are two dynamic hashing schemes originally designed for external files. This paper shows how to adapt these two methods for hash tables stored in main memory. The necessary data structures and algorithms are described, the expected performance is analyzed mathematically, and actual execution times are obtained and compared with alternative techniques. Linear hashing is found to be both faster and easier to implement than spiral storage. Two alternative techniques are considered: a simple unbalanced binary tree and double hashing with periodic rehashing into a larger table. The retrieval time of linear hashing is similar to double hashing and substantially faster than a binary tree, except for very small trees. The loading times of double hashing (with periodic reorganization), a binary tree, and linear hashing are similar. Overall, linear hashing is a simple and efficient technique for applications where the cardinality of the key set is not known in advance.
