Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 36 Issue 4, Oct. 1989

Using temporal hierarchies to efficiently maintain large temporal databases
Thomas Dean
Pages: 687-718
DOI: 10.1145/76359.76360
Many real-world applications involve the management of large amounts of time-dependent information. Temporal database systems maintain this information in order to support various sorts of inference (e.g., answering questions involving...

Spacefilling curves and the planar travelling salesman problem
Loren K. Platzman, John J. Bartholdi, III
Pages: 719-737
DOI: 10.1145/76359.76361
To construct a short tour through points in the plane, the points are sequenced as they appear along a spacefilling curve. This heuristic consists essentially of sorting, so it is easily coded and requires only...

The periodic balanced sorting network
Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael Saks
Pages: 738-757
DOI: 10.1145/76359.76362
A periodic sorting network consists of a sequence of identical blocks. In this paper, the periodic balanced sorting network, which consists of log n blocks, is introduced. Each block, called a balanced merging block, merges...

A transaction-based approach to relational database specification
Serge Abiteboul, Victor Vianu
Pages: 758-789
DOI: 10.1145/76359.76363
An operational approach to database specification is proposed and investigated. Valid database states are described as the states resulting from the application of admissible transactions, specified by a transactional schema....

A uniform approach toward handling atomic and structured information in the nested relational database model
Marc Gyssens, Dirk van Gucht
Pages: 790-825
DOI: 10.1145/76359.76364
The algebras and query languages for nested relations defined thus far do not allow us to “flatten” a relation scheme by disregarding the internal representation of data. In real life, however, the degree in which the structure of...

On the design of some systolic algorithms
Jan L. A. van de Snepscheut, Johan B. Swenker
Pages: 826-840
DOI: 10.1145/76359.76365
The design of systolic algorithms is discussed, that is, algorithms that may efficiently be executed by a synchronous array of cells that perform local communications only. Systolic algorithms are designed through techniques developed in the...

Passes, sweeps, and visits in attribute grammars
Joost Engelfriet, Gilberto Filé
Pages: 841-869
DOI: 10.1145/76359.76366
Theoretical results are presented on multi-pass (both left-to-right and alternating), multi-sweep, and multi-visit attribute grammars. For each of these, a pure type and a simple type are distinguished: The pure attribute grammars are defined by...

The conjecture of Fliess on commutative context-free languages
Juha Kortelainen
Pages: 870-872
DOI: 10.1145/76359.76367
The conjecture of Fliess concerning commutative context-free languages is disproved using a counterexample. ...

Finding minimum-cost circulations by canceling negative cycles
Andrew V. Goldberg, Robert E. Tarjan
Pages: 873-886
DOI: 10.1145/76359.76368
A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious...

Distributed bisimulations
Ilaria Castellani, Matthew Hennessy
Pages: 887-911
DOI: 10.1145/76359.76369
A new equivalence between concurrent processes is proposed. It generalizes the well-known bisimulation equivalence to take into account the distributed nature of processes. The result is a noninterleaving semantic theory; concurrent processes...

P-uniform circuit complexity
Eric W. Allender
Pages: 912-928
DOI: 10.1145/76359.76370
Much complexity-theoretic work on parallelism has focused on the class NC, which is defined in terms of logspace-uniform circuits. Yet P-uniform circuit complexity is in some ways a more natural setting for studying feasible parallelism. In this...

Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer, A. Ehrenfeucht, David Haussler, Manfred K. Warmuth
Pages: 929-965
DOI: 10.1145/76359.76371
Valiant's learnability model is extended to learning classes of concepts defined by regions in Euclidean space En. The methods in this paper lead to a unified treatment of some of Valiant's results, along...