Search
Join ACM

Artificial Intelligence and Machine Learning

Advertisement

Research and Advances

Natural language with discrete speech as a mode for human-to-machine

A voice interactive natural language system, which allows users to solve problems with spoken English commands, has been constructed. The system utilizes a commercially available discrete speech recognizer which requires that each word be followed by approximately a 300 millisecond pause. In a test of the system, subjects were able to learn its use after about two hours of training. The system correctly processed about 77 percent of the over 6000 input sentences spoken in problem-solving sessions. Subjects spoke at the rate of about three sentences per minute and were able to effectively use the system to complete the given tasks. Subjects found the system relatively easy to learn and use, and gave a generally positive report of their experience.
, , , and
Research and Advances

Computing in the home: shifts in the time allocation patterns of households

An empirical study of 282 users of home computers was conducted to explore the relationship between computer use and shifts in time allocation patterns in the household. Major changes in time allocated to various activities were detected. Prior experience with computers (i.e., prior to purchase of the home computer) was found to have a significant impact on the time allocation patterns in the household. The study provides evidence that significant behavior changes can occur when people adopt personal computers in their homes.
, , and
Research and Advances

A generalized implicit enumeration algorithm for graph coloring

A generalized algorithm for graph coloring by implicit enumeration is formulated. A number of backtracking sequential methods are discussed in terms of the generalized algorithm. Some are revealed to be partially correct and inexact. A few corrections to the invalid algorithms, which cause these algorithms to guarantee optimal solutions, are proposed. Finally, some computational results and remarks on the practical relevance of improved implicit enumeration algorithms are given.
and
Research and Advances

Amortized analyses of self-organizing sequential search heuristics

The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilistically. In this article, we use amortization to analyze the heuristics in a worst-case sense; the relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses.
and
Research and Advances

A specification language to assist in analysis of discrete event simulation models

Effective development environments for discrete event simulation models should reduce development costs and improve model performance. A model specification language used in a model development environment is defined. This approach is intended to reduce modeling costs by interposing an intermediate form between a conceptual model (the model as it exists in the mind of the modeler) and an executable representation of that model. As a model specification is constructed, the incomplete specification can be analyzed to detect some types of errors and to provide some types of model documentation. The primitives used in this specification language, called a condition specification (CS), are carefully defined. A specification for the classical patrolling repairman model is used to illustrate this language. Some possible diagnostics and some untestable model specification properties, based on such a representation, are summarized.
and
Research and Advances

Amortized efficiency of list update and paging rules

In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes &thgr;(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.
and

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