Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 31 Issue 3, July 1984

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