Search ACM DL

Search Issue

enter search term and/or author name

**A Mechanical Proof of the Unsolvability of the Halting Problem**

Robert S. Boyer, J. Strother Moore

Pages: 441-458

DOI: 10.1145/828.1882

**Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems**

Yuri Gurevich, Larry Stockmeyer, Uzi Vishkin

Pages: 459-473

DOI: 10.1145/828.322439

**An End-to-End Approach to the Resequencing Problem**

François Baccelli, Erol Gelenbe, Brigitte Plateau

Pages: 474-485

DOI: 10.1145/828.1883

**Synthesis of a Class of Deadlock-Free Petri Nets**

Ajoy Datta, S. Ghosh

Pages: 486-506

DOI: 10.1145/828.322441

**Efficient Schemes for Parallel Communication**

Eli Upfal

Pages: 507-517

DOI: 10.1145/828.1892

**The Format Model**: A Theory of database Organization

Richard Hull, Chee K. Yap

Pages: 518-544

DOI: 10.1145/828.832

A mathematical theory for the study of data representation in databases is introduced and developed. The theory focuses on three data constructs (collection, composition and classification). "Formats" with semantically rich yet tractable...

**Storing a Sparse Table with 0(1) Worst Case Access Time**

Michael L. Fredman, János Komlós, Endre Szemerédi

Pages: 538-544

DOI: 10.1145/828.1884

**On the Optimal Solution of Large Linear Systems**

J. F. Traub, H. Woźniakowski

Pages: 545-559

DOI: 10.1145/828.830

The information-based study of the optimal solution of large linear systems is initiated by studying the case of Krylov information. Among the algorithms that use Krylov information are minimal residual, conjugate gradient, Chebyshev, and...

**A Theory of Communicating Sequential Processes**

S. D. Brookes, C. A. R. Hoare, A. W. Roscoe

Pages: 560-599

DOI: 10.1145/828.833

A mathematical model for communicating sequential processes is given, and a number of its interesting and useful properties are stated and proved. The possibilities of nondetermimsm are fully taken into account.

**A Formal Method for the Abstract Specification of Software**

John McLean

Pages: 600-627

DOI: 10.1145/828.829

An intuitive presentation of the trace method for the abstract specification of software contains sample specifications, syntactic and semantic definitions of consistency and totalness, methods for proving specifications consistent and total,...

**Analysis of interleaved storage via a constant-service queuing system with Markov-chain-driven input**

Micha Hofri

Pages: 628-648

DOI: 10.1145/828.2513

A popular means of increasing the effective rate of main storage accesses in a large computer is a multiplicity of memory modules accessible in parallel. Although such an organization usually achieves a net gain in access rate, it also creates...

**Graph Problems on a Mesh-Connected Processor Array**

Mikhail J. Atallah, S. Rao Kosaraju

Pages: 649-667

DOI: 10.1145/828.322449

**A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem**

Friedhelm Meyer auf der Heide

Pages: 668-676

DOI: 10.1145/828.322450