Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


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