#### Journal of the ACM (JACM), Volume 37 Issue 1, Jan. 1990

**Some computational aspects of circumscription**

Phokion G. Kolaitis, Christos H. Papadimitriou

Pages: 1-14

DOI: 10.1145/78935.78936

The effects of circumscribing first-order formulas are explored from a computational standpoint. First, extending work of V. Lifschitz, it is Shown that the circumscription of any existential first-order formula is equivalent to a first-order...

**Polynomial-time implication problems for unary inclusion dependencies**

Stavros S. Cosmadakis, Paris C. Kanellakis, Moshe Y. Vardi

Pages: 15-46

DOI: 10.1145/78935.78937

Unary inclusion dependencies are database constraints expressing subset relationships. The decidability of implication for these dependencies together with embedded implicational dependencies, such as functional dependencies, are investigated....

**Minimal and complete word unification**

Joxan Jaffar

Pages: 47-85

DOI: 10.1145/78935.78938

The fundamental satisfiability problem for word equations has been solved recently by Makanin. However, this algorithm is purely a decision algorithm. The main result of this paper solves the complementary problem of generating the set of all...

**Completeness of rewrite rules and rewrite strategies for FP**

Joseph Y. Halpern, John H. Williams, Edward L. Wimmers

Pages: 86-143

DOI: 10.1145/78935.78939

This paper treats languages whose operational semantics is given by a set of rewrite rules. For such languages, it is important to be able to determine that there are enough rules to be able to compute the correct meaning of all expressions, but...

**Asymptotic expansion for large closed queuing networks**

Charles Knessl, Charles Tier

Pages: 144-174

DOI: 10.1145/78935.78940

In this paper, a new asymptotic method is developed for analyzing closed BCMP queuing networks with a single class (chain) consisting of a large number of customers, a single infinite server queue, and a large number of single server queues with...

**Nondeterministic polynomial-time computations and models of arithmetic**

Attila Máté

Pages: 175-193

DOI: 10.1145/78935.78941

A semantic, or model theoretic, approach is proposed to study the problems P =? NP and NP =? co-NP. This approach seems to avoid the difficulties that recursion-theoretic approaches appear to face in view of the result of Baker et al. on...