Search
Join ACM

Computing Applications

Advertisement

Research and Advances Mar 1 1983

On the modeling of parallel access to shared data

A model is constructed of a database that can be accessed and modified concurrently by a number of users, and an approximate solution is presented. The resource allocation policies considered involve dynamic acquisition of entities and locking; deadlock is avoided by limiting the number of consecutive attempts to acquire a particular entity. The accuracy of the approximation is evaluated by simulations. Several generalizations aimed at improving the practicality of the model are described.
, , and
Research and Advances Feb 1 1983

On the synthesis of decision tables

Synthesis of decision rules, each depicting a part of a decision process, is necessary in order to know the decision process in total perspective and to validate the consistency and the correctness of the decision logic. This paper proposes a method to synthesize a set of decision tables, each one of them representing a part of the decision logic, and thus serves as a tool for the system analyst in the system design phase.
Research and Advances Feb 1 1983

The computational metaphor and quantum physics

Concurrent computational systems, viewed as sets of cooperating processes, are shown to have close analogies in the world of quantum physics. In particular, analogies exist between processes and particles, between a process' state and a particle's mass, between a process'state changes and a particle's velocity, and between interprocess communications and particle interactions. This view allows the application in the computational world of special relativity theory, the uncertainty principle, the law of conservation of momentum, and many of particle physics' fundamental results. This paper describes the basic analogy and some fundamental results. It is the authors' belief that new insights into a computational processes will be gained as the analogy is developed and vice versa. It is conceivable that established results of the computational sciences may contribute to a new understanding of some of the problems of physics. Other process-oriented sciences, such as biology, economics, and psychology, could also benefit from such development.
and
Research and Advances Feb 1 1983

Regulation of electronic funds transfer: impact and legal issues

This paper investigates the implications and impact of current legislation on the future of the electronic funds transfer systems (EFT). The relevant statutes are introduced and analyzed. Problem areas are discussed together with examples of court rulings. The investigation reveals that the regulations do not provide enough safeguards for the consumer and do not clear up the ambiguities from a combination of competing laws, regulations, and conflicting jurisdictions. Legislators, on both the national and state level, and federal and state governments need to cooperate more closely to produce uniform legislation that specifically addresses the current problems in an EFT environment. Courts need to realize the legislature's intent and the benefits that can be gained before ruling on the current issues.
Research and Advances Feb 1 1983

Some factors affecting program repair maintenance: an empirical study

An empirical study of 447 operational commercial and clerical Cobol programs in one Australian organization and two U.S. organizations was carried out to determine whether program complexity, programming style, programmer quality, and the number of times a program was released affected program repair maintenance. In the Australian organization only program complexity and programming style were statistically significant. In the two U.S. organizations only the number of times a program was released was statistically significant. For all organizations repair maintenance constituted a minor problem: over 90 percent of the programs studied had undergone less than three repair maintenance activities during their lifetime.
and
Research and Advances Dec 1 1982

Software engineering for the Cobol environment

In a attempt to improve the productivity of their 70 development staff, Skandinaviska Enskilda Banken has built an integrated set of manual and automatic tools for the implementation of Cobol programs. It was possible to use a number of modern programming techniques, including software engineering methods, in a Cobol environment. The project required 31 person-months; the aims, current status, and initial results are reported.
Research and Advances Dec 1 1982

On the emulation of flowcharts by decision tables

Any flowchart can be emulated by a decision table, whose complexity depends on that of the flowchart. It may be necessary, however, to introduce a new control variable with associated tests and sets or to permit changes in execution sequences provided action-test independence holds. Two measures of decision table complexity are discussed and interrelated. Finally, conditions and procedures for reducing complexity are presented.
Research and Advances Dec 1 1982

A hash code method for detecting and correcting spelling errors

The most common spelling errors are one extra letter, one missing letter, one wrong letter, or the transposition of two letters. Deletion, exchange, and rotation operators are defined which detect and “mend” such spelling errors and thus permit retrieval despite the errors. These three operators essentially delete a letter of a word, exchange two adjacent letters, and rotate a word cyclically. Moreover, the operators can be used in conjunction with hashing, thus permitting very fast retrieval. Results of experiments run on large databases in Hebrew and in English are briefly indicated.
and
Opinion Dec 1 1982

ACM forum

This is a comment on “File Archival Techniques Using Data Compression” by Michael Pechura [Communications, Sept. 1982, p. 605]. We approached the data compression problem with the aim of maximizing the saving in archival storage over all files for which archival storage was necessary. We also wanted a routine which was reasonably economic in use of system resource.
Research and Advances Dec 1 1982

A critique of the foundations of Hoare style programming logics

Much recent discussion in computing journals has been devoted to arguments about the feasibility and usefulness of formal verification methods. Too little attention has been given to precise criticism of specific proposed systems for reasoning about programs. Whether such systems are to be used for formal verification, by hand or automatically, or as a rigorous foundation for informal reasoning, it is essential that they be logically sound. Several popular rules in the Hoare language are, in fact, not sound. These rules have been accepted because they have not been subjected to sufficiently strong standards of correctness. This paper attempts to clarify the different technical definitions of correctness of a logic, to show that only the strongest of these definitions is acceptable for Hoare logic, and to correct some of the unsound rules that have appeared in the literature. The corrected rules are given merely to show that it is possible to do so. Convenient and elegant rules for reasoning about certain programming constructs will probably require a more flexible notation than Hoare's.
Research and Advances Dec 1 1982

An effective way to represent quadtrees

A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, (i) encoding a pixel from a 2n × 2>n array (or screen) into its quaternary code; (ii) finding adjacent nodes; (iii) determining the color of a node; (iv) superposing two images. It is shown that algorithms (i)-(iii) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.
Research and Advances Dec 1 1982

Implementations for coalesced hashing

The coalesced hashing method is one of the faster searching methods known today. This paper is a practical study of coalesced hashing for use by those who intend to implement or further study the algorithm. Techniques are developed for tuning an important parameter that relates the sizes of the address region and the cellar in order to optimize the average running times of different implementations. A value for the parameter is reported that works well in most cases. Detailed graphs explain how the parameter can be tuned further to meet specific needs. The resulting tuned algorithm outperforms several well-known methods including standard coalesced hashing, separate (or direct) chaining, linear probing, and double hashing. A variety of related methods are also analyzed including deletion algorithms, a new and improved insertion strategy called varied-insertion, and applications to external searching on secondary storage devices.
Research and Advances Nov 1 1982

HISDL—a structure description language

The features of a language designed for the description of the structure of computer systems are described. The structure of a system is specified hierarchically as an interconnection of components with each component being a named instance of a component type. The system itself is another component type. The interconnection between components is specified in two ways: either by specifying all the ports that are connected together, or by specifying a component and the ports that are connected to its ports. A structure specification is a list of such connection specifications. The language has an iterative construct for specifying highly regular structures, and a conditional construct is also provided. A component type can be recursively specified while parameterization of component type specifications is supported. The latter is particularly useful for specifying classes of components of similar structure.
Research and Advances Nov 1 1982

The impact of office automation on the organization: some implications for research and practice

Computer technology has recently been applied to the automation of office tasks and procedures. Much of the technology is aimed not at improving the efficiency of current office procedures, but at altering the nature of office work altogether. The development of automated office systems raises a number of issues for the organization. How will this technology be received by organization members? How will it affect the definition of traditional office work? What will be its impact on individuals, work groups, and the structure of the organization? This paper presents a descriptive model and propositions concerning the potential impacts of office automation on the organization and it stresses the need, when implementing automated office systems, to take a broad perspective of their potential positive and negative effects on the organization. The need for further research examining the potential effects of office automation is emphasized.
and
Research and Advances Nov 1 1982

The distribution of granule accesses made by database transactions

The problem of characterizing the number of granules (or blocks) accessed by a transaction is important in modeling the performance of database management systems and other applications. Different expressions for this quantity have appeared in the literature under different probabilistic assumptions. These expressions along with one new result are presented with a uniform notation and a clear statement of the assumptions underlying each. The partial order relating the predictions of the expected number of granules accessed is presented.
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