Search
Join ACM

Artificial Intelligence and Machine Learning

Advertisement

Research and Advances

MINI-EXEC: a portable executive for 8-bit microcomputers

As microprocessor systems and single-chip microcomputers become more complex, so do the software systems developed for them. In many cases, software is being designed that incorporates multiple control functions running asynchronously on a single microprocessor. Here, discussion focuses on the motivation for running such multiple functions under the control of a real-time multitasking executive. A successfully implemented executive whose design is portable and suitable for use on most 8-bit microprocessors is presented.
Research and Advances

Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues

The volume, moments of inertia, and similar properties of solids are defined by triple (volumetric) integrals over subsets of three-dimensional Euclidean space. The automatic computation of such integral properties for geometrically complex solids is important in CAD/CAM, robotics, and other fields and raises interesting mathematical and computational problems that have received little attention from numerical analysts and computer scientists. This paper summarizes the known methods for calculating integral properties of solids that may be geometrically complex and identifies some significant gaps in our current knowledge.
and
Research and Advances

Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation

This paper discusses a family of algorithms for computing the volume, moments of inertia, and other integral properties of geometrically complex solids, e.g. typical mechanical parts. The algorithms produce approximate decompositions of solids into cuboid cells whose integral properties are easy to compute. The paper focuses on versions of the algorithms which operate on solids represented by Constructive Solid Geometry (CSG), i.e., as set-theoretical combinations of primitive solid “building blocks.” Two known algorithms are summarized and a new algorithm is presented. The efficiencies and accuracies of the three algorithms are analyzed theoretically and compared experimentally. The new algorithm uses recursive subdivision to convert CSG representations of complex solids into approximate cellular decompositions based on variably sized blocks. Experimental data show that the new algorithm is efficient and has predictable accuracy. It also has other potential applications, e.g., in producing approximate octree representations of complex solids and in robot navigation.
and
Opinion

Letters to the editor: A protection model and its implementation in a dataflow system

A protection model is presented for a general purpose computing system based on tags attached as seals and signatures to values exchanged among processes. A tag attached to a value as a seal does not prevent that value from being propagated to any place within the system; rather, it guarantees that the value and any information derived from it cannot leave the system unless a matching tag is presented. A tag attached to a value as a signature is used by a process to verify the origin of the received data. Solutions to problems from the areas of interprocess communication and proprietary services are given.
Research and Advances

Efficient parallel algorithms for some graph problems

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log2 n) time bound can be achieved using only K = n⌈n/log2 n⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
, , and
Research and Advances

A program testing assistant

This paper describes the design and implementation of a program testing assistant which aids a programmer in the definition, execution, and modification of test cases during incremental program development. The testing assistant helps in the interactive definition of test cases and executes them automatically when appropriate. It modifies test cases to preserve their usefulness when the program they test undergoes certain types of design changes. The testing assistant acts as a fully integrated part of the programming environment and cooperates with existing programming tools such as a display editor, compiler, interpreter, and debugger.
Research and Advances

Programmers use slices when debugging

Computer programmers break apart large programs into smaller coherent pieces. Each of these pieces: functions, subroutines, modules, or abstract datatypes, is usually a contiguous piece of program text. The experiment reported here shows that programmers also routinely break programs into one kind of coherent piece which is not coniguous. When debugging unfamiliar programs programmers use program pieces called slices which are sets of statements related by their flow of data. The statements in a slice are not necessarily textually contiguous, but may be scattered through a program.
Research and Advances

Computer rendering of stochastic models

A recurrent problem in generating realistic pictures by computers is to represent natural irregular objects and phenomena without undue time or space overhead. We develop a new and powerful solution to this computer graphics problem by modeling objects as sample paths of stochastic processes. Of particular interest are those stochastic processes which previously have been found to be useful models of the natural phenomena to be represented. One such model applicable to the representation of terrains, known as “fractional Brownian motion,” has been developed by Mandelbrot. The value of a new approach to object modeling in computer graphics depends largely on the efficiency of the techniques used to implement the model. We introduce a new algorithm that computes a realistic, visually satisfactory approximation to fractional Brownian motion in faster time than with exact calculations. A major advantage of this technique is that it allows us to compute the surface to arbitrary levels of details without increasing the database. Thus objects with complex appearances can be displayed from a very small database. The character of the surface can be controlled by merely modifying a few parameters. A similar change allows complex motion to be created inexpensively.
, , and
Research and Advances

Grapevine: an exercise in distributed computing

Grapevine is a multicomputer system on the Xerox research internet. It provides facilities for the delivery of digital messages such as computer mail; for naming people, machines, and services; for authenticating people and machines; and for locating services on the internet. This paper has two goals: to describe the system itself and to serve as a case study of a real application of distributed computing. Part I describes the set of services provided by Grapevine and how its data and function are divided among computers on the internet. Part II presents in more detail selected aspects of Grapevine that illustrate novel facilities or implementation techniques, or that provide insight into the structure of a distributed system. Part III summarizes the current state of the system and the lesson learned from it so far.
, , , and
Research and Advances

A technique for testing command and control software

A technique for testing embedded-microprocessor command and control programs is described. The continuity inherent in functions computed by programs which monitor natural phenomena is exploited by a simple difference equation-based algorithm to predict a program's next output from its preceding ones. The predicted output is compared with the actual output while indexing through the program's domain. Outputs which cannot be predicted are flagged as potential errors. Data are presented which show that this technique can be a sensitive measure of a program's correctness.
Research and Advances

The “worm” programs—early experience with a distributed computation

The “worm” programs were an experiment in the development of distributed computations: programs that span machine boundaries and also replicate themselves in idle machines. A “worm” is composed of multiple “segments,” each running on a different machine. The underlying worm maintenance mechanisms are responsible for maintaining the worm—finding free machines when needed and replicating the program for each additional segment. These techniques were successfully used to support several real applications, ranging from a simple multimachine test program to a more sophisticated real-time animation system harnessing multiple machines.
and
Research and Advances

Generating gamma variates by a modified rejection technique

A suitable square root transformation of a gamma random variable with mean a ≥ 1 yields a probability density close to the standard normal density. A modification of the rejection technique then begins by sampling from the normal distribution, being able to accept and transform the initial normal observation quickly at least 85 percent of the time (95 percent if a ≥ 4). When used with efficient subroutines for sampling from the normal and exponential distributions, the resulting accurate method is significantly faster than competing algorithms.
and
Research and Advances

DIAGRAM: a grammar for dialogues

An explanatory overview is given of DIAGRAM, a large and complex grammar used in an artificial intelligence system for interpreting English dialogue. DIAGRAM is an augmented phrase-structure grammar with rule procedures that allow phrases to inherit attributes from their constituents and to acquire attributes from the larger phrases in which they themselves are constituents. These attributes are used to set context-sensitive constraints on the acceptance of an analysis. Constraints can be imposed by conditions on dominance as well as by conditions on constituency. Rule procedures can also assign scores to an analysis to rate it as probable or unlikely. Less likely analyses can be ignored by the procedures that interpret the utterance. For every expression it analyzes, DIAGRAM provides an annotated description of the structure. The annotations supply important information for other parts of the system that interpret the expression in the context of a dialogue. Major design decisions are explained and illustrated. Some contrasts with transformational grammars are pointed out and problems that motivate a plan to use metarules in the future are discussed. (Metarules derive new rules from a set of base rules to achieve the kind of generality previously captured by transformational grammars but without having to perform transformations on syntactic analyses.)

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More