Journal of the ACM -- 1986

Volume 33, Number 1, January 1986

• Zohar Manna and Richard Waldinger. Special relations in automated deduction. Journal of the ACM, 33(1):1-59, January 1986. [BibTeX entry]

• K. Mehlhorn and F. P. Preparata. Routing through a rectangle. Journal of the ACM, 33(1):60-85, January 1986. Citations. [BibTeX entry]

• Benny Chor, Charles E. Leiserson, Ronald L. Rivest, and James B. Shearer. An application for number theory to the organization of raster-graphics memory. Journal of the ACM, 33(1):86-104, January 1986. [BibTeX entry]

• Marc H. Graham, Alberto O. Mendelzon, and Moshe Y. Vardi. Notions of dependency satisfaction. Journal of the ACM, 33(1):105-129, January 1986. Citations. [BibTeX entry]

• Boris Lubachevsky and Debasis Mitra. A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius. Journal of the ACM, 33(1):130-150, January 1986. [BibTeX entry]

• E. Allen Emerson and Joseph Y. Halpern. ``Sometimes'' and ``not never'' revisited: On branching versus linear time temporal logic. Journal of the ACM, 33(1):151-178, January 1986. Citations. [BibTeX entry]

• Derek L. Eager and Kenneth C. Sevcik. Bound hierarchies for multiple-class queuing networks. Journal of the ACM, 33(1):179-206, January 1986. [BibTeX entry]

• Appie van de Liefvoort and Lester Lipsky. A matrix-algebraic solution to two K_m servers in a loop. Journal of the ACM, 33(1):207-223, January 1986. [BibTeX entry]

• David Harel. Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness. Journal of the ACM, 33(1):224-248, January 1986. Citations. [BibTeX entry]

Volume 33, Number 2, April 1986

• Vincent J. Digricoli and Malcolm C. Harrison. Equality-based binary resolution. Journal of the ACM, 33(2):253-289, April 1986. Citations. [BibTeX entry]

• Takao Asano, Tetsuo Asano, and Hiroshi Imai. Partitioning a polygonal region into trapezoids. Journal of the ACM, 33(2):290-312, April 1986. Citations. [BibTeX entry]

• Leslie Lamport. The mutual exclusion problem: Part I -- a theory of interprocess communication. Journal of the ACM, 33(2):313-326, April 1986. Citations. [BibTeX entry]

• Leslie Lamport. The mutual exclusion problem: Part II -- statement and solutions. Journal of the ACM, 33(2):327-348, April 1986. Citations. [BibTeX entry]

• Raymond Reiter. A sound and sometimes complete query evaluation algorithm for relational databases with null values. Journal of the ACM, 33(2):349-370, April 1986. Citations. [BibTeX entry]

• Philippe Flajolet and Claude Puech. Partial match retrieval of multidimensional data. Journal of the ACM, 33(2):371-407, April 1986. Citations. [BibTeX entry]

Volume 33, Number 3, July 1986

• Serge Abiteboul and Seymour Ginsburg. Tuple sequences and lexicographic indexes. Journal of the ACM, 33(3):409-422, July 1986. [BibTeX entry]

• Catriel Beeri and Michael Kifer. Elimination of intersection anomalies from database schemes. Journal of the ACM, 33(3):423-450, July 1986. [BibTeX entry]

• Francis Chin. Security problems on inference control for SUM, MAX, and MIN queries. Journal of the ACM, 33(3):451-446, July 1986. [BibTeX entry]

• Seymour Ginsburg and Richard Hull. Sort sets in the relational model. Journal of the ACM, 33(3):465-488, July 1986. [BibTeX entry]

• Luc Devroye. A note on the height of binary search trees. Journal of the ACM, 33(3):489-498, July 1986. Citations. [BibTeX entry]

• Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):499-516, July 1986. Citations. [BibTeX entry]

• Thomas F. Coleman, Anders Edenbrandt, and John R. Gilbert. Predicting fill for sparse orthogonal factorization. Journal of the ACM, 33(3):517-532, July 1986. [BibTeX entry]

• Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximate algorithms for bottleneck problems. Journal of the ACM, 33(3):533-550, July 1986. Citations. [BibTeX entry]

• Samar Singh. Improved methods for storing and updating information in the out-of-kilter algorithm. Journal of the ACM, 33(3):551-567, July 1986. [BibTeX entry]

• Debasis Mitra and J. McKenna. Asymptotic expansions for closed Markovian networks with state-dependent service rates. Journal of the ACM, 33(3):568-592, July 1986. Citations. [BibTeX entry]

• John N. Tsitsiklis, Christos H. Papadimitriou, and Pierre Humblet. The performance of a precedence-based queuing discipline. Journal of the ACM, 33(3):593-602, July 1986. Citations. [BibTeX entry]

• Jose L. Balcázar, Ronald V. Book, and Uwe Schöning. The polynomial-time hierarchy and sparse oracles. Journal of the ACM, 33(3):603-617, July 1986. Citations. [BibTeX entry]

• Timothy J. Long and Alan L. Selman. Relativizing complexity classes with sparse oracles. Journal of the ACM, 33(3):618-627, July 1986. Citations. [BibTeX entry]

Volume 33, Number 4, October 1986

• Dennis de Champeaux. Subproblem finder and instance checker, two cooperating modules for theorem provers. Journal of the ACM, 33(4):633-657, October 1986. [BibTeX entry]

• W. Eric L. Grimson. The combinatorics of local constraints in model-based recognition and localization from sparse data. Journal of the ACM, 33(4):658-686, October 1986. [BibTeX entry]

• Vijaya Ramachandran. On driving many long wires in a VLSI layout. Journal of the ACM, 33(4):687-701, October 1986. [BibTeX entry]

• R. Chaudhuri and A. N. V. Rao. Approximating grammar probabilities: Solution of a conjecture. Journal of the ACM, 33(4):702-705, October 1986. Citations. [BibTeX entry]

• Bruce Jay Collings and G. Barry Hembree. Initializing generalized feedback shift register pseudorandom number generators. Journal of the ACM, 33(4):706-711, October 1986. Citations. [BibTeX entry]

• M. Cosnard and Y. Robert. Complexity of parallel QR factorization. Journal of the ACM, 33(4):712-723, October 1986. Citations. [BibTeX entry]

• K. R. Apt and G. D. Plotkin. Countable nondeterminism and random assignment. Journal of the ACM, 33(4):724-767, October 1986. Citations. [BibTeX entry]

• A. E. Conway and N. D. Georganas. RECAL -- a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks. Journal of the ACM, 33(4):768-791, October 1986. Citations. [BibTeX entry]

• Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, October 1986. Citations. [BibTeX entry]

• R. Kannan and R. J. Lipton. Polynomial-time algorithm for the orbit problem. Journal of the ACM, 33(4):808-821, October 1986. [BibTeX entry]

• John H. Rowland and John R. Cowles. Small sample algorithms for the identification of polynomials. Journal of the ACM, 33(4):822-829, October 1986. [BibTeX entry]

Shortcuts: