Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 34 Issue 2, April 1987

Inference with path resolution and semantic graphs
Neil V. Murray, Erik Rosenthal
Pages: 225-254
DOI: 10.1145/23005.23716
A graphical representation of quantifier-free predicate calculus formulas in negation normal form and a new rule of inference that employs this representation are introduced. The new rule, path resolution, is an amalgamation of...

Recognizing planar perfect graphs
Wen-Lian Hsu
Pages: 255-288
DOI: 10.1145/23005.31330
An O(n3) algorithm for recognizing planar graphs that do not contain induced odd cycles of length greater than 3 (odd holes) is presented. A planar graph with this property satisfies the...

Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
Albert G. Greenberg, Philippe Flajolet, Richard E. Ladner
Pages: 289-325
DOI: 10.1145/23005.23006
New, improved algorithms are proposed for regulating access to a multiple-access channel, a common channel shared by many geographically distributed computing stations. A conflict of multiplicity n occurs when n...

Optimal reconfiguration strategy for a degradable multimodule computing system
Yann-Hang Lee, Kang G. Shin
Pages: 326-348
DOI: 10.1145/23005.23016
A new quantitative approach to the problem of reconfiguring a degradable multimodule system is presented. The approach is concerned with both assigning some modules for computation and arranging others for reliability. Conventionally, a...

Answering queries on embedded-complete database schemes
Edward P. F. Chan, Alberto O. Mendelzon
Pages: 349-375
DOI: 10.1145/23005.23007
It has been observed that, for some database schemes, users may have difficulties retrieving correct information, even for simple queries. The problem occurs when some implicit “piece” of information, defined on some subset of a...

Associative table lookup processing for multioperand residue arithmetic
Christos A. Papachristou
Pages: 376-396
DOI: 10.1145/23005.23017
This paper investigates the complexity of multioperand residue addition and multiplication implemented by associative table lookup processing. The complexity measure used is the size of the associative memory, that is, the number of matching...

Linear probing with a nonuniform address distribution
Georg Ch. Pflug, Hans W. Kessler
Pages: 397-410
DOI: 10.1145/23005.42225
This paper presents a new approach to the analysis of hashing with linear probing for nonuniformly distributed hashed keys. The use of urn models is avoided. Instead, some facts about empirical processes, which are well known in statistics are...

A model for distributed systems based on graph rewriting
Pierpaolo Degano, Ugo Montanari
Pages: 411-449
DOI: 10.1145/23005.24038
In our model, a graph describes a net of processes communicating through ports and, at the same time, its computation history consisting of a partial ordering of events. Stand-alone evolution of processes is specified by context-free...

Concurrent dynamic logic
David Peleg
Pages: 450-479
DOI: 10.1145/23005.23008
In this paper concurrent dynamic logic (CDL) is introduced as an extension of dynamic logic tailored toward handling concurrent programs. Properties of CDL are discussed, both on the propositional and first-order level, and the extension is...

Minimal degrees for polynomial reducibilities
Steven Homer
Pages: 480-491
DOI: 10.1145/23005.23009
The existence of minimal degrees is investigated for several polynomial reducibilities. It is shown that no set has minimal degree with respect to polynomial many-one or Turing reducibility. This extends a result of Ladner in which only...

Decidability of the purely existential fragment of the theory of term algebras
K. N. Venkataraman
Pages: 492-510
DOI: 10.1145/23005.24037
This paper is concerned with the question of the decidability and the complexity of the decision problem for certain fragments of the theory of free term algebras. The existential fragment of...