Strategic computing at DARPA: overview and assessment
Strategic Computing, a 10-year initiative to build faster and more intelligent systems, is ambitious, flawed by overscheduling perhaps and problems of definition, but basically sound.
Computing Applications
Advertisement
Environmental and institutional models of system development: a national criminal history system
This article tests two competing theories of system development referred to here as environmental and institutional models. These models form the basis for most explanations of why systems are developed and utilized. We will examine both models in detail and apply them to a single set of data concerned with the emerging national computerized criminal history system (CCH). A hybrid model, which combines elements of environmental and institutional approaches, is also developed and tested. A substantive result of this new model will alter our understanding of why a national CCH system is being developed. At the theoretical level, we conclude that a hybrid model is more powerful than either an environmental or an institutional model taken separately and that future research must take this into account.
Transient exponential-Erlang queues and steady-state simulation
The transient probabilistic structure of M/Em/1 and Em/M/1 queues initialized in an arbitrary deterministic state is derived in discrete time. Computational algorithms for obtaining the required probabilities are provided, and their application in calculating a variety of system performance measures is illustrated. The results are used to investigate the question of initializing simulations of systems such as these to promote rapid convergence to steady state, if that is the object of the simulation. These results are consistent with earlier studies for transient queueing systems, such as the M/M/s, but allow greater flexibility in specification of interarrival or service-time models inherent in the Erlang distributions.
On time and space decomposition of complex structures
Models of large and complex systems can often be reduced to smaller sub-models, for easier analysis, by a process known as decomposition. Certain criteria for successful decompositions can be established.
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.
Toward automating the software-development cycle
Knowledge-intensive rather than labor-intensive processes are being advanced to spur programming productivity.
Computing programs in small colleges
This Summary Report of The ACM Small College Task Force outlines resources, courses, and problems for small colleges developing degree programs in computing.
Data compression using static Huffman code-decode tables
Both static and dynamic Huffman coding techniques are applied to test data consisting of 530 source programs in four different languages. The results indicate that, for small files, a savings of 22-91 percent in compression can be achieved by using the static instead of dynamic techniques.
A randomized protocol for signing contracts
Randomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined.The 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. The first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received.An implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.
A generalized user interface for applications programs (II)
A display-screen management system for user interaction with an arbitrary application program is simple enough so that the end user controls the dialogue and screens yet powerful enough to provide for user specification of screen geometry, input constraints, computation facilities, and display logic—quite independently of the application system.
An application of queueing theory to the design of a message-switching computer system
Inexact or real-world queueing techniques are used to determine that the number of buffers provided in system design is indeed adequate to guard against message loss.
A polynomial time generator for minimal perfect hash functions
A perfect hash function PHF is an injection F from a set W of M objects into the set consisting of the first N nonnegative integers where N ⩾ M. If N = M, then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language.The mincycle algorithm for finding PHFs executes with an expected time complexity that is polynomial in M and has been used successfully on sets of cardinality up to 512. Given three pseudorandom functions h0, h1, and h2, the mincycle algorithm searches for a function g such that F(w) = (h0(w) + g ° h1(w) + g ° h2(w)) mod N is a PHF.
A self-assessment procedure dealing with the legal issues of computing
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 InvolvedCommunications 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