Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 44 Issue 2, March 1997

Semiring-based constraint satisfaction and optimization
Stefano Bistarelli, Ugo Montanari, Francesca Rossi
Pages: 201-236
DOI: 10.1145/256303.256306
We introduce a general framework for constraint satisfaction and optimization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where...

Two heads are better than two tapes
Tao Jiang, Joel I. Seiferas, Paul M. B. Vitányi
Pages: 237-256
DOI: 10.1145/256303.256308
We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set.

Dynamic word problems
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum
Pages: 257-271
DOI: 10.1145/256303.256309

On the completeness of object-creating database transformation languages
Jan Van Den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens
Pages: 272-319
DOI: 10.1145/256303.256311
Object-oriented applications of database systems require database transformations involoving nonstandard functionalities such as set manipulation and object creation, that is, the introduction of new domain elements. To deal with thse...

Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution
W. Bibel, E. Eder
Pages: 320-344
DOI: 10.1145/256303.256313
This paper addresses and answers a fundamental question about resolution. Informally, what is gained with respect to the search for a proof by performing a single resolution step? It is first shown that any unsatisfiable formula may be...

Evaluating uniform expressions within two steps of minimum parallel time
Robert A. Wagner
Pages: 345-361
DOI: 10.1145/256303.256314
Consider an array of Processing Elements [PEs], connected by a 2-dimensional grid network, and holding at most one operand of an expression in each PE. Suppose that each PE is allowed, in any one parallel step, to receive one item of data from...