**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...