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