Journal of the ACM -- 1984

Volume 31, Number 1, January 1984

• Robert E. Shostak. Deciding combinations of theories. Journal of the ACM, 31(1):1-12, January 1984. Citations. [BibTeX entry]

• H. J. Hooever, M. M. Klawe, and N. J. Pippenger. Bounding fan-out in logical networks. Journal of the ACM, 31(1):13-18, January 1984. [BibTeX entry]

• Peter Eades, Michael Hickey, and Ronald C. Read. Some Hamilton paths and a minimal change algorithm. Journal of the ACM, 31(1):19-29, January 1984. Citations. [BibTeX entry]

• Catriel Beeri, Martin Dowd, Ronald Fagin, and Richard Statman. On the structure of Armstrong relations for functional dependencies. Journal of the ACM, 31(1):30-46, January 1984. Citations. [BibTeX entry]

• Lawrence J. Henschen and Shamim A. Naqvi. On compiling queries in recursive first-order databases. Journal of the ACM, 31(1):47-85, January 1984. Citations. [BibTeX entry]

• Aurel A. Lazar. Optimal flow control of an M/M/m queue. Journal of the ACM, 31(1):86-98, January 1984. [BibTeX entry]

• Sidnie Dresher Feit. A fast algorithm for the two-variable integer programming problem. Journal of the ACM, 31(1):99-113, January 1984. Citations. [BibTeX entry]

• Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, January 1984. Citations. [BibTeX entry]

• O. J. Boxma, F. P. Kelly, and A. G. Konheim. The product form for sojourn time distributions in cyclic exponential queues. Journal of the ACM, 31(1):128-133, January 1984. [BibTeX entry]

• B. Simon. Priority queues with feedback. Journal of the ACM, 31(1):134-149, January 1984. [BibTeX entry]

• J. Ja'Ja' and V. K. Prasanna Kumar. Information transfer in distributed computing with applications to VLSI. Journal of the ACM, 31(1):150-162, January 1984. Citations. [BibTeX entry]

• Douglas R. Smith. Random trees and the analysis of branch and bound procedures. Journal of the ACM, 31(1):163-188, January 1984. [BibTeX entry]

Volume 31, Number 2, April 1984

• Allan Gottlieb and Clyde P. Kruskal. Complexity results for permuting data and other computations on parallel processors. Journal of the ACM, 31(2):193-209, April 1984. Citations. [BibTeX entry]

• Richard Hull. Finitely specifiable implicational dependency families. Journal of the ACM, 31(2):210-226, April 1984. [BibTeX entry]

• Mihalis Yannakakis. Serializability by locking. Journal of the ACM, 31(2):227-244, April 1984. Citations. [BibTeX entry]

• Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245-281, April 1984. Citations. [BibTeX entry]

• Karel Culik II and Tero Harju. The omega-sequence equivalence problem for D0L systems is decidable. Journal of the ACM, 31(2):282-298, April 1984. [BibTeX entry]

• H. B. Hunt III. Terminating Turing machine computations and the complexity and/or decidability of correspondence problems, grammars, and program schemes. Journal of the ACM, 31(2):299-318, April 1984. Citations. [BibTeX entry]

• C. W. Clenshaw and F. W. J. Olver. Beyond floating point. Journal of the ACM, 31(2):319-328, April 1984. [BibTeX entry]

• George M. Trojan. Lower bounds and fast algorithms for sequence acceleration. Journal of the ACM, 31(2):329-335, April 1984. [BibTeX entry]

• Hans Röck. The three-machine no-wait flow shop is NP-complete. Journal of the ACM, 31(2):336-345, April 1984. [BibTeX entry]

• J. McKenna and Debasis Mitra. Asymptotic expansions and integral representations of moments of queue lengths in closed Markovian networks. Journal of the ACM, 31(2):346-360, April 1984. Citations. [BibTeX entry]

• Akeo Adachi, Shigeki Iwata, and Takumi Kasai. Some combinatorial game problems require Omega(n^k) time. Journal of the ACM, 31(2):361-376, April 1984. [BibTeX entry]

• Joseph Ja'Ja'. The VLSI complexity of selected graph problems. Journal of the ACM, 31(2):377-391, April 1984. Citations. [BibTeX entry]

• Christos H. Papadimitriou. On the complexity of unique solutions. Journal of the ACM, 31(2):392-400, April 1984. Citations. [BibTeX entry]

• John H. Reif. Symmetric complementation. Journal of the ACM, 31(2):401-421, April 1984. Citations. [BibTeX entry]

• John E. Savage. Space-time trade-offs for banded matrix problems. Journal of the ACM, 31(2):422-437, April 1984. [BibTeX entry]

Volume 31, Number 3, July 1984

• Robert S. Boyer and J Strother Moore. A mechanical proof of the unsolvability of the halting problem. Journal of the ACM, 31(3):441-458, July 1984. [BibTeX entry]

• Yuri Gurevich, Larry Stockmeyer, and Uzi Vishkin. Solving NP-hard problems on graphs that are almost trees and an application to facility location problems. Journal of the ACM, 31(3):459-473, July 1984. Citations. [BibTeX entry]

• François Baccelli, Erol Gelenbe, and Brigitte Plateau. An end-to-end approach to the resequencing problem. Journal of the ACM, 31(3):474-485, July 1984. Citations. [BibTeX entry]

• Ajoy Datta and S. Ghosh. Synthesis of a class of deadlock-free Petri nets. Journal of the ACM, 31(3):486-506, July 1984. [BibTeX entry]

• Eli Upfal. Efficient schemes for parallel communication. Journal of the ACM, 31(3):507-517, July 1984. Citations. [BibTeX entry]

• Richard Hull and Chee K. Yap. The format model: A theory of database organization. Journal of the ACM, 31(3):518-537, July 1984. Citations. [BibTeX entry]

• Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3):538-544, July 1984. Citations. [BibTeX entry]

• J. F. Traub and H. Wo\'zniakowski. On the optimal solution of large linear systems. Journal of the ACM, 31(3):545-559, July 1984. Citations. [BibTeX entry]

• S. D. Brookes, C. A. R. Hoare, and A. W. Roscoe. A theory of communicating sequential processes. Journal of the ACM, 31(3):560-599, July 1984. Citations. [BibTeX entry]

• John McLean. A formal method for the abstract specification of software. Journal of the ACM, 31(3):600-627, July 1984. [BibTeX entry]

• Micha Hofri. Analysis of interleaved storage via a constant-service queuing system with Markov-chain-driven input. Journal of the ACM, 31(3):628-648, July 1984. [BibTeX entry]

• Mikhail J. Atallah and S. Rao Kosaraju. Graph problems on a mesh-connected processor array. Journal of the ACM, 31(3):649-667, July 1984. [BibTeX entry]

• Friedhelm Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM, 31(3):668-676, July 1984. Citations. [BibTeX entry]

Volume 31, Number 4, October 1984

• S. G. Williamson. Depth-first search and Kuratowski subgraphs. Journal of the ACM, 31(4):681-693, October 1984. Citations. [BibTeX entry]

• Jonathan W. Greene and Abbas El Gamal. Configuration of VLSI arrays in the presence of defects. Journal of the ACM, 31(4):694-717, October 1984. Citations. [BibTeX entry]

• Catriel Beeri and Moshe Y. Vardi. A proof procedure for data dependencies. Journal of the ACM, 31(4):718-741, October 1984. Citations. [BibTeX entry]

• Stavros S. Cosmadakis and Christos H. Papadimitriou. Updates of relational views. Journal of the ACM, 31(4):742-760, October 1984. [BibTeX entry]

• Tomasz Imieli\'nski and Witold Lipski, Jr.. Incomplete information in relational databases. Journal of the ACM, 31(4):761-791, October 1984. Citations. [BibTeX entry]

• A. Boja\'nczyk. Optimal asynchronous Newton method for the solution of nonlinear equations. Journal of the ACM, 31(4):792-803, October 1984. [BibTeX entry]

• P.-J. Courtois and P. Semal. Bounds for the positive eigenvectors of nonnegative matrices and for their approximations by decomposition. Journal of the ACM, 31(4):804-825, October 1984. Citations. [BibTeX entry]

• A. R. Calderbank, E. G. Coffman, Jr., and L. Flatto. Optimum head separation in a disk system with two read/write heads. Journal of the ACM, 31(4):826-838, October 1984. Citations. [BibTeX entry]

• Benjamin Melamed and Micha Yadin. Numerical computation of sojourn-time distributions in queuing networks. Journal of the ACM, 31(4):839-854, October 1984. [BibTeX entry]

• Debasis Mitra and P. J. Weinberger. Probabilistic models of database locking: Solutions, computational algorithms, and asymptotics. Journal of the ACM, 31(4):855-878, October 1984. [BibTeX entry]

• P. A. Bloniarz, H. B. Hunt, III, and D. J. Rosenkrantz. Algebraic structures with hard equivalence and minimization problems. Journal of the ACM, 31(4):879-904, October 1984. Citations. [BibTeX entry]

• J. Pachl, E. Korach, and D. Rotem. Lower bounds for distributed maximum-finding algorithms. Journal of the ACM, 31(4):905-918, October 1984. Citations. [BibTeX entry]

Shortcuts: