. German Research Center for Artificial Intelligence GmbH

Persistent Bibliographic Information Record
s0004-5411

Journal of the ACM

Description:

The Journal of the ACM (JACM) is a publication medium for original research papers of lasting value in computer science. Submissions are judged primarily on originality, significance, and breadth of interest. To be accepted, a paper must be judged to be truly outstanding in its field.

On-line Access:

Information concerning the journal is available from Association for Computing Machinery

PBIR:

The unique LIDOS PBIR Identifier is s0004-5411

URL:

This page is located at http://www.dfki.uni-sb.de/imedia/lidos/pbir/s0004-5411.html

PURL:

Hyperlinks to this page should refer to http://purl.org/dfki/pbir/s0004-5411.html, the persistent URL of this bibliographic information record

Contents:

1

A. Bagchi and A. Mahanti. Three Approaches to Heuristic Search in Networks. Journal of the ACM, 32(1):1-27, January 1985.

2

A. Mahanti and A. Bagchi. AND/OR Graph Heuristic Search Methods. Journal of the ACM, 32(1):28-51, January 1985.

3

Leslie Lamport and P. M. Melliar-Smith. Synchronizing Clocks in the Presence of Faults. Journal of the ACM, 32(1):52-78, January 1985.

4

Serge Abiteboul. Disaggregations in Databases. Journal of the ACM, 32(1):79-101, January 1985.

5

Ken Fuchs and Dennis Kafura. Memory-Constrained Task Scheduling on a Network of Dual Processors. Journal of the ACM, 32(1):102-129, January 1985.

6

Dorit S. Hochbaum and Wolfgang Maass. Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. Journal of the ACM, 32(1):130-136, January 1985.

7

Matthew Hennessy and Robin Milner. Algebraic Laws for Nondeterminism and Concurrency. Journal of the ACM, 32(1):137-161, January 1985.

8

Hendrik Vantilborgh. Aggregation with an Error of O(e**2). Journal of the ACM, 32(1):162-190, January 1985.

9

Danny Dolev and Rüdiger Reischuk. Bounds on Information Exchange for Byzantine Agreement. Journal of the ACM, 32(1):191-204, January 1985.

10

Shimon Even, Alan L. Selman, and Yacov Yacobi. Hard-Core Theorems for Complexity Classes. Journal of the ACM, 32(1):205-217, January 1985.

11

Maria M. Klawe. A Tight Bound for Black and White Pebbles on the Pyramid. Journal of the ACM, 32(1):218-228, January 1985.

12

J. C. Lagarias and A. M. Odlyzko. Solving Low-Density Subset Sum Problems. Journal of the ACM, 32(1):229-246, January 1985.

13

M. A. Bauer. Soundness and Completeness of a Synthesis Algorithm Based on Example Computations. Journal of the ACM, 32(2):249-279, April 1985.

14

G. Gottlob and A. Leitsch. On the Efficiency of Subsumption Algorithms. Journal of the ACM, 32(2):280-295, April 1985.

15

Ching-Chy Wang, Errol L. LLoyd, and Mary Lou Soffa. Feedback Vertex Sets and Cyclically Reducible Graphs. Journal of the ACM, 32(2):296-313, April 1985.

16

G. N. Buckley and A. Silberschatz. Beyond Two-Phase Locking. Journal of the ACM, 32(2):314-326, April 1985.

17

Brenda S. Baker, Edward G. Coffman, Jr., and Dan E. Willard. Algorithms for Resolving Conflicts in Dynamic Storage Allocation. Journal of the ACM, 32(2):327-343, April 1985.

18

M. E. Gonzalez Smith and J. A. Storer. Parallel Algorithms for Data Compression. Journal of the ACM, 32(2):344-373, April 1985.

19

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2):374-382, April 1985.

20

G. Cornuéjols, D. Naddef, and W. Pulleyblank. The Traveling Salesman Problem in Graphs with 3-Edge Cutsets. Journal of the ACM, 32(2):383-410, April 1985.

21

John Staples and V. L. Nguyen. A Fixpoint Semantics for Nondeterministic Data Flow. Journal of the ACM, 32(2):411-444, April 1985.

22

Asser N. Tantawi and Don Towsley. Optimal Static Load Balancing in Distributed Computer Systems. Journal of the ACM, 32(2):445-465, April 1985.

23

Eitan M. Gurari. Decidable Problems for Powerful Programs. Journal of the ACM, 32(2):466-483, April 1985.

24

S. Skyum and L. G. Valiant. A Complexity Theory Based on Boolean Algebra. Journal of the ACM, 32(2):484-502, April 1985.

25

Rina Dechter and Judea Pearl. Generalized Best-First Search Strategies and the Optimality of A*. Journal of the ACM, 32(3):505-536, July 1985.

26

Edward A. Bender and Jon T. Butler. Enumeration of Structured Flowcharts. Journal of the ACM, 32(3):537-548, July 1985.

27

William H. Cunningham. Optimal Attach and Reinforcement of a Network. Journal of the ACM, 32(3):549-561, July 1985.

28

C. C. Lee and D. T. Lee. A Simple On-Line Bin-Packing Algorithm. Journal of the ACM, 32(3):562-572, July 1985.

29

Bernard Chazelle and Louis Monier. A Model of Computation for VLSI with Related Complexity Results. Journal of the ACM, 32(3):573-588, July 1985.

30

Albert G. Greenberg and Shmuel Winograd. A Lower Bound on the Time Needed in the Worst Case to Resolve Conflicts Deterministically in Multiple Access Channels. Journal of the ACM, 32(3):589-596, July 1985.

31

Dan E. Willard and George S. Lueker. Adding Range Restriction Capability to Dynamic Data Structures. Journal of the ACM, 32(3):597-617, July 1985.

32

Y. C. Tay, Rajan Suri, and Nathan Goodman. A Mean Value Performance Model for Locking in Databases: The No-Waiting Case. Journal of the ACM, 32(3):618-651, July 1985.

33

Daniel Dominic Sleator and Robert Endre Tarjan. Self-Adjusting Binary Search Trees. Journal of the ACM, 32(3):652-686, July 1985.

34

Andrew C. Yao. Uniform Hashing Is Optimal. Journal of the ACM, 32(3):687-693, July 1985.

35

David Zerling. Generating Binary Trees Using Rotations. Journal of the ACM, 32(3):694-701, July 1985.

36

Wei-Lu Cao and William J. Stewart. Iterative Aggregation/Disaggregation Techniques for Nearly Uncoupled Markov Chains. Journal of the ACM, 32(3):702-719, July 1985.

37

Udi Manber and Martin Tompa. The Complexity of Problems on Probabilistic Nondeterministic, and Alternating Decision Trees. Journal of the ACM, 32(3):720-732, July 1985.

38

A. P. Sistla and E. M. Clarke. The Complexity of Propositional Linear Temporal Logics. Journal of the ACM, 32(3):733-749, July 1985.

39

Christos H. Papadimitriou. Correction to ``A Theorem in Database Concurrency Control''. Journal of the ACM, 32(3):750, July 1985.

40

Eugene C. Freuder. A Sufficient Condition for Backtrack-Bounded Search. Journal of the ACM, 32(4):755-761, October 1985.

41

Richard M. Karp and Avi Wigderson. A Fast Parallel Algorithm for the Maximal Independent Set Problem. Journal of the ACM, 32(4):762-773, October 1985.

42

Domenico Saccà. Closures of Database Hypergraphs. Journal of the ACM, 32(4):774-803, October 1985.

43

Baruch Awerbuch. Complexity of Network Synchronization. Journal of the ACM, 32(4):804-823, October 1985.

44

Gabriel Bracha and Sam Toueg. Asynchronous Consensus and Broadcast Protocols. Journal of the ACM, 32(4):824-840, October 1985.

45

Hector Garcia-Molina and Daniel Barbara. How to Assign Votes in a Distributed System. Journal of the ACM, 32(4):841-860, October 1985.

46

Ulrich Faigle. On Ordered Languages and the Optimization of Linear Functions by Greedy Algorithms. Journal of the ACM, 32(4):861-870, October 1985.

47

Ilan Adler and Nimrod Megiddo. A Simplex Algorithm Whose Average Number of Steps Is Bounded between Two Quadratic Functions of the Smaller Dimension. Journal of the ACM, 32(4):871-895, October 1985.

48

M. Hennessy. Acceptance Trees. Journal of the ACM, 32(4):896-928, October 1985.

49

Friedhelm Meyer auf der Heide. Lower Bounds for Solving Linear Diophantine Equations on Random Access Machines. Journal of the ACM, 32(4):929-937, October 1985.

50

Shlomo Moran, Marc Snir, and Udi Manber. Applications of Ramsey's Theorem to Decision Tree Complexity. Journal of the ACM, 32(4):938-949, October 1985.

51

Mihalis Yannakakis. A Polynomial Algorithm for the Min-Cut Linear Arrangement of Trees. Journal of the ACM, 32(4):950-988, October 1985.

52

Zohar Manna and Richard Waldinger. Special Relations in Automated Deduction. Journal of the ACM, 33(1):1-59, January 1986.

53

K. Mehlhorn and F. P. Preparata. Routing through a Rectangle. Journal of the ACM, 33(1):60-85, January 1986.

54

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.

55

Marc H. Graham, Alberto O. Mendelzon, and Moshe Y. Vardi. Notions of Dependency Satisfaction. Journal of the ACM, 33(1):105-129, January 1986.

56

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.

57

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.

58

Derek L. Eager and Kenneth C. Sevcik. Bound Hierarchies for Multiple-Class Queuing Networks. Journal of the ACM, 33(1):179-206, January 1986.

59

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.

60

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.

61

Vincent J. Digricoli and Malcolm C. Harrison. Equality-Based Binary Resolution. Journal of the ACM, 33(2):253-289, April 1986.

62

Takao Asano, Tetsuo Asano, and Hiroshi Imai. Partitioning a Polygonal Region into Trapezoids. Journal of the ACM, 33(2):290-312, April 1986.

63

Leslie Lamport. The Mutual Exclusion Problem: Part I--A Theory of Interprocess Communication. Journal of the ACM, 33(2):313-326, April 1986.

64

Leslie Lamport. The Mutual Exclusion Problem: Part II--Statement and Solutions. Journal of the ACM, 33(2):327-348, April 1986.

65

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.

66

Philippe Flajolet and Claude Puech. Partial Match Retrieval of Multidimensional Data. Journal of the ACM, 33(2):371-407, April 1986.

67

Serge Abiteboul and Seymour Ginsburg. Tuple Sequences and Lexicographic Indexes. Journal of the ACM, 33(3):409-422, July 1986.

68

Catriel Beeri and Michael Kifer. Elimination of Intersection Anomalies from Database Schemes. Journal of the ACM, 33(3):423-450, July 1986.

69

Francis Chin. Security Problems on Inference Control for SUM, MAX, and MIN Queries. Journal of the ACM, 33(3):451-446, July 1986.

70

Seymour Ginsburg and Richard Hull. Sort Sets in the Relational Model. Journal of the ACM, 33(3):465-488, July 1986.

71

Luc Devroye. A Note on the Height of Binary Search Trees. Journal of the ACM, 33(3):489-498, July 1986.

72

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.

73

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.

74

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.

75

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.

76

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.

77

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.

78

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.

79

Timothy J. Long and Alan L. Selman. Relativizing Complexity Classes with Sparse Oracles. Journal of the ACM, 33(3):618-627, July 1986.

80

Dennis de Champeaux. Subproblem Finder and Instance Checker, Two Cooperating Modules for Theorem Provers. Journal of the ACM, 33(4):633-657, October 1986.

81

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.

82

Vijaya Ramachandran. On Driving Many Long Wires in a VLSI Layout. Journal of the ACM, 33(4):687-701, October 1986.

83

R. Chaudhuri and A. N. V. Rao. Approximating Grammar Probabilities: Solution of a Conjecture. Journal of the ACM, 33(4):702-705, October 1986.

84

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.

85

M. Cosnard and Y. Robert. Complexity of Parallel QR Factorization. Journal of the ACM, 33(4):712-723, October 1986.

86

K. R. Apt and G. D. Plotkin. Countable Nondeterminism and Random Assignment. Journal of the ACM, 33(4):724-767, October 1986.

87

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.

88

Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to Construct Random Functions. Journal of the ACM, 33(4):792-807, October 1986.

89

R. Kannan and R. J. Lipton. Polynomial-Time Algorithm for the Orbit Problem. Journal of the ACM, 33(4):808-821, October 1986.

90

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.

91

B. Chazelle and D. P. Dobkin. Intersection of Convex Objects in Two and Three Dimensions. Journal of the ACM, 34(1):1-27, January 1987.

92

Victor Vianu. Dynamic Functional Dependencies and Database Aging. Journal of the ACM, 34(1):28-59, January 1987.

93

John H. Reif and Leslie G. Valiant. A Logarithmic Time Sort for Linear Size Networks. Journal of the ACM, 34(1):60-76, January 1987.

94

Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the Minimal Synchronism Needed for Distributed Consensus. Journal of the ACM, 34(1):77-97, January 1987.

95

Greg N. Frederickson and Nancy A. Lynch. Electing a Leader in a Synchronous Ring. Journal of the ACM, 34(1):98-115, January 1987.

96

Eli Upfal and Avi Wigderson. How to Share Memory in a Distributed System. Journal of the ACM, 34(1):116-127, January 1987.

97

Yoshihito Toyama. On the Church-Rosser Property for the Direct Sum of Term Rewriting Systems. Journal of the ACM, 34(1):128-143, January 1987.

98

Dorit S. Hochbaum and David B. Shmoys. Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. Journal of the ACM, 34(1):144-162, January 1987.

99

Rüdiger Reischuk. Simultaneous WRITES of Parallel Random Access Machines Do Not Help to Compute Simple Arithmetic Functions. Journal of the ACM, 34(1):163-178, January 1987.

100

Lorenzo Donatiello and Balakrishna R. Iyer. Analysis of a Composite Performance Reliability Measure for Fault-Tolerant Systems. Journal of the ACM, 34(1):179-199, January 1987.

101

Richard Cole. Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms. Journal of the ACM, 34(1):200-208, January 1987.

102

Alasdair Urquhart. Hard Examples for Resolution. Journal of the ACM, 34(1):209-219, January 1987.

103

Neil V. Murray and Erik Rosenthal. Inference with Path Resolution and Semantic Graphs. Journal of the ACM, 34(2):225-254, April 1987.

104

Wen-Lian Hsu. Recognizing Planar Perfect Graphs. Journal of the ACM, 34(2):255-288, April 1987.

105

Albert G. Greenberg, Philippe Flajolet, and Richard E. Ladner. Estimating the Multiplicities of Conflicts to Speed Their Resolution in Multiple Access Channels. Journal of the ACM, 34(2):289-325, April 1987.

106

Yann-Hang Lee and Kang G. Shin. Optimal Reconfiguration Strategy for a Degradable Multimodule Computing System. Journal of the ACM, 34(2):326-348, April 1987.

107

Edward P. F. Chan and Alberto O. Mendelzon. Answering Queries on Embedded-Complete Database Schemes. Journal of the ACM, 34(2):349-375, April 1987.

108

Christos A. Papachristou. Associative Table Lookup Processing for Multioperand Residue Arithmetic. Journal of the ACM, 34(2):376-396, April 1987.

109

Georg Ch. Pflug and Hans W. Kessler. Linear Probing with a Nonuniform Address Distribution. Journal of the ACM, 34(2):397-410, April 1987.

110

Pierpaolo Degano and Ugo Montanari. A Model for Distributed Systems Based on Graph Rewriting. Journal of the ACM, 34(2):411-449, April 1987.

111

David Peleg. Concurrent Dynamic Logic. Journal of the ACM, 34(2):450-479, April 1987.

112

Steven Homer. Minimal Degrees for Polynomial Reducibilities. Journal of the ACM, 34(2):480-491, April 1987.

113

K. N. Venkataraman. Decidability of the Purely Existential Fragment of the Theory of Term Algebras. Journal of the ACM, 34(2):492-510, April 1987.

114

Zvi Galil, Christoph M. Hoffmann, Eugene M. Luks, Claus P. Schnorr, and Andreas Weber. An O(n**3 log n) Deterministic and an O(n**3) Las Vegas Isomorphism Test for Trivalent Graphs. Journal of the ACM, 34(3):513-531, July 1987.

115

Robert W. Irving, Paul Leather, and Dan Gusfield. An Efficient Algorithm for the ``Optimal'' Stable Marriage. Journal of the ACM, 34(3):532-543, July 1987.

116

Catriel Beeri and Michael Kifer. A Theory of Intersection Anomalies in Relational Database Schemes. Journal of the ACM, 34(3):544-577, July 1987.

117

A. Blumer, J. Blumer, D. Haussler, R. McConnell, and A. Ehrenfeucht. Complete Inverted Files for Efficient Text Retrieval and Analysis. Journal of the ACM, 34(3):578-595, July 1987.

118

Michael L. Fredman and Robert Endre Tarjan. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM, 34(3):596-615, July 1987.

119

D. S. Hirschberg and L. L. Larmore. New Applications of Failure Functions. Journal of the ACM, 34(3):616-625, July 1987.

120

T. K. Srikanth and Sam Toueg. Optimal Clock Synchronization. Journal of the ACM, 34(3):626-645, July 1987.

121

Stanley Cabay and Bart Domzy. Systems of Linear Equations with Dense Univariate Polynomial Coefficients. Journal of the ACM, 34(3):646-660, July 1987.

122

Randolph Nelson. Stochastic Catastrophe Theory in Computer Performance Modeling. Journal of the ACM, 34(3):661-685, July 1987.

123

Rajan Suri. Infinitesimal Perturbation Analysis for General Discrete Event Systems. Journal of the ACM, 34(3):686-717, July 1987.

124

Ronald V. Book and Ding-Zhu Du. The Existence and Density of Generalized Complexity Cores. Journal of the ACM, 34(3):718-730, July 1987.

125

Michio Oyamaguchi. The Equivalence Problem for Real-Time DPDAs. Journal of the ACM, 34(3):731-760, July 1987.

126

Alfred Inselberg, Tuval Chomut, and Mordechai Reif. Convexity Algorithms in Parallel Coordinates. Journal of the ACM, 34(4):765-801, October 1987.

127

Debasis Mitra and Randall A. Cieslak. Randomized Parallel Communications on an Extension of the Omega Network. Journal of the ACM, 34(4):802-824, October 1987.

128

Jeffrey Scott Vitter. Design and Analysis of Dynamic Huffman Codes. Journal of the ACM, 34(4):825-845, October 1987.

129

Dan E. Willard. Multidimensional Search Trees That Provide New Types of Memory Reductions. Journal of the ACM, 34(4):846-858, October 1987.

130

Joshua J. Bloch, Dean S. Daniels, and Alfred Z. Spector. A Weighted Voting Algorithm for Replicated Directories. Journal of the ACM, 34(4):859-909, October 1987.

131

Gabriel Bracha. An O(log n) Expected Rounds Randomized Byzantine Generals Protocol. Journal of the ACM, 34(4):910-920, October 1987.

132

Prasoon Tiwari. Lower Bounds on Communication Complexity in Distributed Computer Networks. Journal of the ACM, 34(4):921-938, October 1987.

133

Shu Tezuka. On the Discrepancy of GFSR Pseudorandom Numbers. Journal of the ACM, 34(4):939-949, October 1987.

134

Donald B. Johnson. Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks. Journal of the ACM, 34(4):950-967, October 1987.

135

Michael Kaminski. A Linear Time Algorithm for Residue Computation and a Fast Algorithm for Division with a Sparse Divisor. Journal of the ACM, 34(4):968-984, October 1987.

136

James McKenna. Asymptotic Expansions of the Sojourn Time Distribution Functions of Jobs in Closed, Product-Form Queuing Networks. Journal of the ACM, 34(4):985-1003, October 1987.

137

Miklos Ajtai and Yuri Gurevich. Monotone versus Positive. Journal of the ACM, 34(4):1004-1015, October 1987.

138

Y. Sagiv, C. Delobel, D. S. Parker, Jr., and Ronald Fagin. Correction to ``An Equivalence between Relational Database Dependencies and a Fragment of Propositional Logic''. Journal of the ACM, 34(4):1016-1018, October 1987.

139

Christoph Walther. Many-Sorted Unification. Journal of the ACM, 35(1):1-17, January 1988.

140

N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou. The Complexity of Searching a Graph. Journal of the ACM, 35(1):18-44, January 1988.

141

Yann-Hang Lee and Kang G. Shin. Optimal Design and Use of Retry in Fault-Tolerant Computer Systems. Journal of the ACM, 35(1):45-69, January 1988.

142

Serge Abiteboul and Victor Vianu. Equivalence and Optimization of Relational Transactions. Journal of the ACM, 35(1):70-120, January 1988.

143

Vassos Hadzilacos. A Theory of Reliability in Database Systems. Journal of the ACM, 35(1):121-145, January 1988.

144

Anthony Klug. On Conjunctive Queries Containing Inequalities. Journal of the ACM, 35(1):146-160, January 1988.

145

Gaston H. Gonnet and Per-Åke Larson. External Hashing with Limited Internal Storage. Journal of the ACM, 35(1):161-184, January 1988.

146

Timothy Hickey and Jacques Cohen. Automating Program Analysis. Journal of the ACM, 35(1):185-220, January 1988.

147

Satish K. Tripathi and C. Murray Woodside. A Vertex-Allocation Theorem for Resources in Queuing Networks. Journal of the ACM, 35(1):221-230, January 1988.

148

Erich Kaltofen. Greatest Common Divisors of Polynomials Given by Straight-Line Programs. Journal of the ACM, 35(1):231-264, January 1988.

149

Avikam Baltsan and Micha Sharir. On the Shortest Paths between Two Convex Polyhedra. Journal of the ACM, 35(2):267-287, April 1988.

150

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the Presence of Partial Synchrony. Journal of the ACM, 35(2):288-323, April 1988.

151

Robert McNaughton, Paliath Narendran, and Friedrich Otto. Church-Rosser Thue Systems and Formal Languages. Journal of the ACM, 35(2):324-344, April 1988.

152

Jeffrey D. Ullman and Allen Van Gelder. Efficient Tests for Top-Down Termination of Logical Rules. Journal of the ACM, 35(2):345-373, April 1988.

153

Zvi Galil and Éva Tardos. An O(n**2 (m + n log n) log n) Min-Cost Flow Algorithm. Journal of the ACM, 35(2):374-386, April 1988.

154

Galen H. Sasaki and Bruce Hajek. The Time Complexity of Maximum Matching by Simulated Annealing. Journal of the ACM, 35(2):387-403, April 1988.

155

Ravinderpal Singh Sandhu. The Schematic Protection Model: Its Definition and Analysis for Acyclic Attenuating Schemes. Journal of the ACM, 35(2):404-432, April 1988.

156

A. R. Calderbank, E. G. Coffman, Jr., and Leopold Flatto. Optimal Directory Placement on Disk Storage Devices. Journal of the ACM, 35(2):433-446, April 1988.

157

Helmut Alt. Comparing the Combinatorial Complexities of Arithmetic Functions. Journal of the ACM, 35(2):447-460, April 1988.

158

Ingo Wegener. On the Complexity of Branching Programs and Decision Trees for Clique Functions. Journal of the ACM, 35(2):461-471, April 1988.

159

N. Shankar. A Mechanical Proof of the Church-Rosser Theorem. Journal of the ACM, 35(3):475-522, July 1988.

160

Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch. Finding a Maximum-Genus Graph Imbedding. Journal of the ACM, 35(3):523-534, July 1988.

161

Wen-Lian Hsu. The Coloring and Maximum Independent Set Problems on Planar Perfect Graphs. Journal of the ACM, 35(3):535-563, July 1988.

162

Wansoo T. Rhee and Michel Talagrand. Some Distributions That Allow Perfect Packing. Journal of the ACM, 35(3):564-578, July 1988.

163

Jonathan Goodman, Albert G. Greenberg, Neal Madras, and Peter March. Stability of Binary Exponential Backoff. Journal of the ACM, 35(3):579-602, July 1988.

164

Lenwood S. Heath, Arnold L. Rosenberg, and Bruce T. Smith. The Physical Mapping Problem for Parallel Architectures. Journal of the ACM, 35(3):603-634, July 1988.

165

S. Rao Kosaraju and Mikhail J. Atallah. Optimal Simulations between Mesh-Connected Arrays of Processors. Journal of the ACM, 35(3):635-650, July 1988.

166

Faith E. Fich and Martin Tompa. The Parallel complexity of Exponentiating Polynomials over Finite Fields. Journal of the ACM, 35(3):651-667, July 1988.

167

Hans Daduna. Busy Periods for Subnetworks in Stochastic Networks: Mean Value Analysis. Journal of the ACM, 35(3):668-674, July 1988.

168

Jan Robin Rohlicek and Alan S. Willsky. The Reduction of Perturbed Markov Generators: An Algorithm Exposing the Role of Transient States. Journal of the ACM, 35(3):675-696, July 1988.

169

Jik H. Chang, Oscar H. Ibarra, and Anastasios Vergis. On the Power of One-Way Communication. Journal of the ACM, 35(3):697-726, July 1988.

170

Michael R. Fellows and Michael A. Langston. Nonconstructive Tools for Proving Polynomial-Time Decidability. Journal of the ACM, 35(3):727-739, July 1988.

171

Friedhelm Meyer auf der Heide. Fast Algorithms for N-Dimensional Restrictions of Hard Problems. Journal of the ACM, 35(3):740-747, July 1988.

172

Arnold Schönhage. A Nonlinear Lower Bound for Random-Access Machines under Logarithmic Cost. Journal of the ACM, 35(3):748-754, July 1988.

173

Vašek Chvátal and Endre Szemerédi. Many Hard Examples for Resolution. Journal of the ACM, 35(4):759-768, October 1988.

174

M. D. Grigoriadis and B. Kalantari. A New Class of Heuristic Algorithms for Weighed Perfect Matching. Journal of the ACM, 35(4):769-776, October 1988.

175

Richard Cole and Alan Siegel. Optimal VLSI Circuits for Sorting. Journal of the ACM, 35(4):777-809, October 1988.

176

Teofilo F. Gonzalez and Sing-Ling Lee. A Linear Time Algorithm for Optimal Routing around a Rectangle. Journal of the ACM, 35(4):810-831, October 1988.

177

Shivendra S. Panwar, Don Towsley, and Jack K. Wolf. Optimal Scheduling Policies for a Class of Queues with Customer Deadlines to the Beginning of Service. Journal of the ACM, 35(4):832-844, October 1988.

178

Hagit Attiya, Marc Snir, and Manfred K. Warmuth. Computing on an Anonymous Ring. Journal of the ACM, 35(4):845-875, October 1988.

179

Anna R. Karlin and Eli Upfal. Parallel Hashing: An Efficient Implementation of Shared Memory. Journal of the ACM, 35(4):876-892, October 1988.

180

Lyle Ramshaw. Eliminating go to's while Preserving Program Structure. Journal of the ACM, 35(4):893-920, October 1988.

181

Andrew V. Goldberg and Robert E. Tarjan. A New Approach to the Maximum-Flow Problem. Journal of the ACM, 35(4):921-940, October 1988.

182

David A. Mix Barrington and Denis Thérien. Finite Monoids and the Fine Structure of NC1. Journal of the ACM, 35(4):941-952, October 1988.

183

Daniel Leivant and Tim Fernando. Meager and Replete Failures of Relative Completeness. Journal of the ACM, 35(4):953-964, October 1988.

184

Leonard Pitt and Leslie G. Valiant. Computational Limitations on Learning from Examples. Journal of the ACM, 35(4):965-984, October 1988.

185

Joel I. Seiferas and Paul M. B. Vitányi. Counting Is Easy. Journal of the ACM, 35(4):985-1000, October 1988.

186

Bruce Jay Collings and G. Barry Hembree. Addendum to ``Initializing Generalized Feedback Shift Register Pseudorandom Number Generators''. Journal of the ACM, 35(4):1001, October 1988.

187

John H. Muller and Jeremy Spinrad. Incremental Modular Decomposition. Journal of the ACM, 36(1):1-19, January 1989.

188

J. A. Brzozowski and C-J. Seger. A Unified Framework for Race Analysis of Asynchronous Networks. Journal of the ACM, 36(1):20-45, January 1989.

189

William W. McCune and Lawrence J. Henschen. Maintaining State Constraints in Relational Databases: A Proof Theoretic Basis. Journal of the ACM, 36(1):46-68, January 1989.

190

Jeffrey F. Naughton. Minimizing Function-Free Recursive Inference Rules. Journal of the ACM, 36(1):69-91, January 1989.

191

Jens M. Dill. A Counterexample for ``A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars''. Journal of the ACM, 36(1):92-96, January 1989.

192

Paul Helman. A Common Schema for Dynamic Programming and Branch and Bound Algorithms. Journal of the ACM, 36(1):97-128, January 1989.

193

Joan Boyar. Inferring Sequences Produced by Pseudo-Random Number Generators. Journal of the ACM, 36(1):129-141, January 1989.

194

Michael Kaminski. A Note on Probabilistically Verifying Integer and Polynomial Products. Journal of the ACM, 36(1):142-149, January 1989.

195

Michael Kaminski and Nader H. Bshouty. Multiplicative Complexity of Polynomial Multiplication over Finite Fields. Journal of the ACM, 36(1):150-170, January 1989.

196

Edmundo de Souza e Silva and H. Richard Gail. Calculating Availability and Performability Measures of Repairable Computer Systems Using Randomization. Journal of the ACM, 36(1):171-193, January 1989.

197

Edmundo de Souza e Silva and S. S. Lavenberg. Calculating Joint Queue-Length Distributions in Product-Form Queuing Networks. Journal of the ACM, 36(1):194-207, January 1989.

198

John D. Hobby. Rasterizing Curves of Constant Width. Journal of the ACM, 36(2):209-229, April 1989.

199

Catriel Beeri, Philip A. Bernstein, and Nathan Goodman. A Model for Concurrency in Nested Transactions Systems. Journal of the ACM, 36(2):230-269, April 1989.

200

Walter Cunto and J. Ian Munro. Average Case Selection. Journal of the ACM, 36(2):270-279, April 1989.

201

Rolf Klein and Derick Wood. On the Path Length of Binary Trees. Journal of the ACM, 36(2):280-289, April 1989.

202

G. K. Manacher, T. D. Bui, and T. Mai. Optimum Combinations of Sorting and Merging. Journal of the ACM, 36(2):290-334, April 1989.

203

Michael O. Rabin. Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance. Journal of the ACM, 36(2):335-348, April 1989.

204

Arnon Rosenthal and José A. Pino. A Generalized Algorithm for Centrality Problems on Trees. Journal of the ACM, 36(2):349-361, April 1989.

205

G. Bilardi and F. P. Preparata. Size-Time Complexity of Boolean Networks for Prefix Computations. Journal of the ACM, 36(2):362-382, April 1989.

206

L. Pitt. Probabilistic Inductive Inference. Journal of the ACM, 36(2):383-433, April 1989.

207

Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recognizing Circle Graphs in Polynomial Time. Journal of the ACM, 36(3):435-473, July 1989.

208

Thomas Lengauer. Hierarchical Planarity Testing Algorithms. Journal of the ACM, 36(3):474-509, July 1989.

209

David Peleg and Eli Upfal. A Trade-Off between Space and Efficiency for Routing Tables. Journal of the ACM, 36(3):510-530, July 1989.

210

Nicholas Pippenger. Invariance of Complexity Measures for Networks with Unreliable Gates. Journal of the ACM, 36(3):531-539, July 1989.

211

Harold N. Gabow, Zvi Galil, and Thomas H. Spencer. Efficient Implementation of Graph Algorithms Using Contraction. Journal of the ACM, 36(3):540-572, July 1989.

212

Sanjiv Kapoor and Edward M. Reingold. Optimum Lopsided Binary Trees. Journal of the ACM, 36(3):573-590, July 1989.

213

Benny Chor, Michael Merritt, and David B. Shmoys. Simple Constant-Time Consensus Protocols in Realistic Failure Models. Journal of the ACM, 36(3):591-614, July 1989.

214

François Baccelli, William A. Massey, and Don Towsley. Acyclic Fork-Join Queuing Networks. Journal of the ACM, 36(3):615-642, July 1989.

215

Paul Beame and Johan Hastad. Optimal Bounds for Decision Problems on the CRCW PRAM. Journal of the ACM, 36(3):643-670, July 1989.

216

Ming Li and Yaacov Yesha. New Lower Bounds for Parallel Computation. Journal of the ACM, 36(3):671-680, July 1989.

217

Thomas Dean. Using Temporal Hierarchies to Efficiently Maintain Large Temporal Databases. Journal of the ACM, 36(4):687-718, October 1989.

218

Loren K. Platzman and John J. Bartholdi, III. Spacefilling Curves and the Planar Travelling Salesman Problem. Journal of the ACM, 36(4):719-737, October 1989.

219

Martin Dowd, Yehoshua Perl, Larry Rudolph, and Michael Saks. The Periodic Balanced Sorting Network. Journal of the ACM, 36(4):738-757, October 1989.

220

Serge Abiteboul and Victor Vianu. A Transaction-Based Approach to Relational Database Specification. Journal of the ACM, 36(4):758-789, October 1989.

221

Marc Gyssens, Jan Paredaens, and Dirk Van Gucht. A Uniform Approach toward Handling Atomic and Structured Information in the Nested Relational Database Model. Journal of the ACM, 36(4):790-825, October 1989.

222

Jan L. A. van de Snepscheut and Johan B. Swenker. On the Design of Some Systolic Algorithms. Journal of the ACM, 36(4):826-840, October 1989.

223

Joost Engelfriet and Gilberto Filé. Passes, Sweeps, and Visits in Attribute Grammars. Journal of the ACM, 36(4):841-869, October 1989.

224

Juha Kortelainen. The Conjecture of Fliess on Commutative Context-Free Languages. Journal of the ACM, 36(4):870-872, October 1989.

225

Andrew V. Goldberg and Robert E. Tarjan. Finding Minimum-Cost Circulations by Canceling Negative Cycles. Journal of the ACM, 36(4):873-886, October 1989.

226

Ilaria Castellani and Matthew Hennessy. Distributed Bisimulations. Journal of the ACM, 36(4):887-911, October 1989.

227

Eric W. Allender. P-Uniform Circuit Complexity. Journal of the ACM, 36(4):912-928, October 1989.

228

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis Dimension. Journal of the ACM, 36(4):929-965, October 1989.

229

Phokion G. Kolaitis and Christos H. Papadimitriou. Some Computational Aspects of Circumscription. Journal of the ACM, 37(1):1-14, January 1990.

230

Stavros S. Cosmadakis, Paris C. Kanellakis, and Moshe Y. Vardi. Polynomial-Time Implication Problems for Unary Inclusion Dependencies. Journal of the ACM, 37(1):15-46, January 1990.

231

Joxan Jaffar. Minimal and Complete Word Unification. Journal of the ACM, 37(1):47-85, January 1990.

232

Joseph Y. Halpern, John H. Williams, and Edward L. Wimmers. Completeness of Rewrite Rules and Rewrite Strategies for FP. Journal of the ACM, 37(1):86-143, January 1990.

233

Charles Knessl and Charles Tier. Asymptotic Expansions for Large Closed Queuing Networks. Journal of the ACM, 37(1):144-174, January 1990.

234

Attila Máté. Nondeterministic Polynomial-Time Computations and Models of Arithmetic. Journal of the ACM, 37(1):175-193, January 1990.

235

Henry W. Davis. Cost-Error Relationships in A* Tree-Searching. Journal of the ACM, 37(2):195-199, April 1990.

236

Bernard Chazelle. Lower Bounds for Orthogonal Range Searching: I. The Reporting Case. Journal of the ACM, 37(2):200-212, April 1990.

237

Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan. Faster Algorithms for the Shortest Path Problem. Journal of the ACM, 37(2):213-223, April 1990.

238

Béla Bollobás, Andrei Z. Broder, and Istvan Simon. The Cost Distribution of Clustering in Random Probing. Journal of the ACM, 37(2):224-237, April 1990.

239

Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. A Trade-Off between Information and Communication in Broadcast Protocols. Journal of the ACM, 37(2):238-256, April 1990.

240

Maurice Herlihy. Concurrency and Availability as Dual Properties of Replicated Atomic Data. Journal of the ACM, 37(2):257-278, April 1990.

241

Mart´ın Abadi and Zohar Manna. Nonclausal Deduction in First-Order Temporal Logic. Journal of the ACM, 37(2):279-317, April 1990.

242

Farhad Shahrokhi and D. W. Matula. The Maximum Concurrent Flow Problem. Journal of the ACM, 37(2):318-334, April 1990.

243

J. A. Bergstra, J. Heering, and P. Klint. Module Algebra. Journal of the ACM, 37(2):335-372, April 1990.

244

François Baccelli and Zhen Lu. On the Execution of Parallel Programs on Multiprocessor Systems--A Queuing Theory Approach. Journal of the ACM, 37(2):373-414, April 1990.

245

Ker-I Ko. Separating and Collapsing Results on the Relativized Probabilistic Polynomial-Time Hierarchy. Journal of the ACM, 37(2):415-438, April 1990.

246

Bernard Chazelle. Lower Bounds for Orthogonal Range Searching II. The Arithmetic Model. Journal of the ACM, 37(3):439-463, July 1990.

247

Lawrence L. Larmore and Daniel S. Hirschberg. A Fast Algorithm for Optimal Length-Limited Huffman Codes. Journal of the ACM, 37(3):464-473, July 1990.

248

Marc H. Graham and Ke Wang. On the Equivalence of an Egd to a Set of Fd's. Journal of the ACM, 37(3):474-490, July 1990.

249

In Kyung Ryu and Alexander Thomasian. Analysis of Database Performance with Dynamic Locking. Journal of the ACM, 37(3):491-523, July 1990.

250

Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an Asynchronous Environment. Journal of the ACM, 37(3):524-548, July 1990.

251

Joseph Y. Halpern and Yoram Moses. Knowledge and Common Knowledge in a Distributed Environment. Journal of the ACM, 37(3):549-587, July 1990.

252

Aydin Üresin and Michel Dubois. Parallel Asynchronous Algorithms for Discrete Data. Journal of the ACM, 37(3):588-606, July 1990.

253

Ariel Orda and Raphael Rom. Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the ACM, 37(3):607-625, July 1990.

254

Yijie Han and Robert A. Wagner. An Efficient and Fast Parallel-Connected Component Algorithm. Journal of the ACM, 37(3):626-642, July 1990.

255

K. R. Pattipati, M. M. Kostreva, and J. L. Teele. Approximate Mean Value Analysis Algorithms for Queuing Networks: Existence, Uniqueness, and Convergence Results. Journal of the ACM, 37(3):643-673, July 1990.

256

Yuri Gurevich and Saharon Shelah. Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space. Journal of the ACM, 37(3):674-687, July 1990.

257

Wojciech Szpankowski. Patricia Tries Again Revisited. Journal of the ACM, 37(4):691-711, October 1990.

258

David A. Briggs. A Correction of the Termination Conditions of the Henschen-Naqvi Technique. Journal of the ACM, 37(4):712-719, October 1990.

259

Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. Early Stopping in Byzantine Agreement. Journal of the ACM, 37(4):720-741, October 1990.

260

Tobias Nipkow. Unification in Primal Algebras, Their Powers and Their Varieties. Journal of the ACM, 37(4):742-776, October 1990.

261

Gopalan Nadathur and Dale Miller. Higher-Order Horn Clauses. Journal of the ACM, 37(4):777-814, October 1990.

262

J. R. B. Cockett and J. A. Hierrera. Decision Tree Reduction. Journal of the ACM, 37(4):815-842, October 1990.

263

Dorit S. Hochbaum and J. George Shanthikumar. Convex Separable Optimization Is Not Much Harder than Linear Optimization. Journal of the ACM, 37(4):843-862, October 1990.

264

Peter G. Harrison and Naresh M. Patel. The Representation of Multistage Interconnection Networks in Queuing Models of Parallel Systems. Journal of the ACM, 37(4):863-898, October 1990.

265

Martin Dyer, Alan Frieze, and Ravi Kannan. A Random Polynomial-Time Algorithm for Approximating the Volume of Convex Bodies. Journal of the ACM, 38(1):1-17, January 1991.

266

Joseph S. B. Mitchell and Christos H. Papadimitriou. The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision. Journal of the ACM, 38(1):18-73, January 1991.

267

Ketan Mulmuley. A Fast Planar Partition Algorithm, II. Journal of the ACM, 38(1):74-103, January 1991.

268

Dan E. Willard. Optimal Sample Cost Residues for Differential Database Batch Query Problems. Journal of the ACM, 38(1):104-119, January 1991.

269

Yehoshua Sagiv. Evaluation of Queries in Independent Database Schemes. Journal of the ACM, 38(1):120-161, January 1991.

270

Greg N. Frederickson. Planar Graph Decomposition and All Pairs Shortest Paths. Journal of the ACM, 38(1):162-204, January 1991.

271

V. Chandru and J. N. Hooker. Extended Horn Sets in Propositional Logic. Journal of the ACM, 38(1):205-221, January 1991.

272

Gloria Kissin. Upper and Lower Bounds on Switching Energy in VLSI. Journal of the ACM, 38(1):222-254, January 1991.

273

E. M. Arkin, C. H. Papadimitriou, and M. Yannakakis. Modularity of Cycles and Paths in Graphs. Journal of the ACM, 38(2):255-274, April 1991.

274

David Dobkin and Subhash Suri. Maintenance of Geometric Extrema. Journal of the ACM, 38(2):275-298, April 1991.

275

Randal E. Bryant. A Methodology for Hardware Verification Based on Logic Simulation. Journal of the ACM, 38(2):299-328, April 1991.

276

Yannis E. Ioannidis and Eugene Wong. Towards an Algebraic Theory of Recursion. Journal of the ACM, 38(2):329-381, April 1991.

277

Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi. A Model-Theoretic Analysis of Knowledge. Journal of the ACM, 38(2):382-428, April 1991.

278

Nicholas Bambos and Jean Walrand. On Stability and Performance of Parallel Processing Systems. Journal of the ACM, 38(2):429-452, April 1991.

279

Yishay Mansour, Baruch Schieber, and Prasoon Tiwari. A Lower Bound for Integer Greatest Common Divisor Computations. Journal of the ACM, 38(2):453-471, April 1991.

280

Anne Condon. Space-Bounded Probabilistic Game Automata. Journal of the ACM, 38(2):472-494, April 1991.

281

Noga Alon, A. K. Dewdney, and Teunis J. Ott. Efficient Simulation of Finite Automata by Neural Nets. Journal of the ACM, 38(2):495-514, April 1991.

282

Tom Leighton. Letter From the Editor. Journal of the ACM, 38(3):515, July 1991.

283

Mikhail J. Atallah, Danny Z. Chen, and Hubert Wagener. An Optimal Parallel Algorithm for the Visibility of a Simple Polygon from a Point. Journal of the ACM, 38(3):516-533, July 1991.

284

Tomasz Imielinski. Abstraction in Query Processing. Journal of the ACM, 38(3):534-558, July 1991.

285

Jieh Hsiang and Michaël Rusinowitch. Proving Refutational Completeness of Theorem-Proving Strategies: The Transfinite Semantic Tree Method. Journal of the ACM, 38(3):559-587, July 1991.

286

Wiktor Marek and Miroslaw Truszczynski. Autoepistemic Logic. Journal of the ACM, 38(3):588-619, July 1991.

287

Allen Van Gelder, Kenneth A. Ross, and John S. Schlipf. The Well-Founded Semantics for General Logic Programs. Journal of the ACM, 38(3):620-650, July 1991.

288

Maxime Crochemore and Dominique Perrin. Two-Way String-Matching. Journal of the ACM, 38(3):651-675, July 1991.

289

Keith W. Ross and David D. Yao. Optimal Load Balancing and Scheduling in a Distributed Computer System. Journal of the ACM, 38(3):676-690, July 1991.

290

Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. Journal of the ACM, 38(3):691-729, July 1991.

291

Cüneyt M. Özveren, Alan S. Willsky, and Panos J. Antsaklis. Stability and Stabilizability of Discrete Event Dynamic Systems. Journal of the ACM, 38(3):730-752, July 1991.

292

Jacobo Torán. Complexity Classes Defined by Counting Quantifiers. Journal of the ACM, 38(3):753-774, July 1991.

293

Bradley S. Stewart and Chelsea C. White, III. Multiobjective A*. Journal of the ACM, 38(4):775-814, October 1991.

294

Harold N. Gabow and Robert E. Tarjan. Faster Scaling Algorithms for General Graph-Matching Problems. Journal of the ACM, 38(4):815-853, October 1991.

295

Edward P. F. Chan and Héctor J. Hernández. Independence-Reducible Database Schemes. Journal of the ACM, 38(4):854-886, October 1991.

296

Stephen L. Bloom and Zoltá Ésik. Floyd-Hoare Logic in Iteration Theories. Journal of the ACM, 38(4):887-934, October 1991.

297

Joseph Y. Halpern and Yoav Shoham. A Propositional Modal Logic of Time Intervals. Journal of the ACM, 38(4):935-962, October 1991.

298

Michael Tiomkin and Michael Kaminski. Nonmonotonic Default Modal Logics. Journal of the ACM, 38(4):963-984, October 1991.

299

Egon Balas, Donald Miller, Joseph Pekny, and Paolo Toth. A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem. Journal of the ACM, 38(4):985-1004, October 1991.

300

Paul Glasserman. Structural Conditions for Perturbation Analysis of Queuing Systems. Journal of the ACM, 38(4):1005-1025, October 1991.

301

Bonnie Berger and John Rompel. Simulating (log**c n)-Wise Independence in NC. Journal of the ACM, 38(4):1026-1046, October 1991.

302

Bernard Chazelle and Herbert Edelsbrunner. An Optimal Algorithm for Intersecting Line Segments in the Plane. Journal of the ACM, 39(1):1-54, January 1992.

303

Eli Upfal. An O(log N) Deterministic Packet-Routing Scheme. Journal of the ACM, 39(1):55-70, January 1992.

304

Robert Demolombe. Syntactical Characterization of a Subset of Domain-Independent Formulas. Journal of the ACM, 39(1):71-94, January 1992.

305

Joseph A. Goguen and Rod M. Burstall. Institutions: Abstract Model Theory for Specification and Programming. Journal of the ACM, 39(1):95-146, January 1992.

306

L. Aceto and M. Hennessy. Termination, Deadlock, and Divergence. Journal of the ACM, 39(1):147-187, January 1992.

307

Lawrence W. Dowdy, Brian M. Carlson, Alan T. Krantz, and Satish K. Tripathi. Single-Class Bounds of Multi-Class Queuing Networks. Journal of the ACM, 39(1):188-213, January 1992.

308

Mihir Bellare and Silvio Micali. How to Sign Given Any Trapdoor Permutation. Journal of the ACM, 39(1):214-233, January 1992.

309

Eric Allender and Lane A. Hemachandra. Lower Bounds for the Low Hierarchy. Journal of the ACM, 39(1):234-251, January 1992.

310

Michael B. Dillencourt, Hannan Samet, and Markku Tamminen. A General Approach to Connected-Component Labeling for Arbitrary Image Representations. Journal of the ACM, 39(2):253-280, April 1992.

311

Jyrki Katajainen and Timo Raita. An Analysis of the Longest Match and the Greedy Heuristics in Text Encoding. Journal of the ACM, 39(2):281-294, April 1992.

312

R. Ramesh and I. V. Ramakrishnan. Nonlinear Pattern Matching in Trees. Journal of the ACM, 39(2):295-316, April 1992.

313

Renzo Sprugnoli. The Generation of Binary Trees as a Numerical Problem. Journal of the ACM, 39(2):317-327, April 1992.

314

Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi. What Can Machines Know? On the Properties of Knowledge in Distributed Systems. Journal of the ACM, 39(2):328-376, April 1992.

315

Jean Gallier, Paliath Narendran, Stan Raatz, and Wayne Snyder. Theorem Proving Using Equational Matings and Rigid E-Unification. Journal of the ACM, 39(2):377-429, April 1992.

316

Gene Myers. A Four Russians Algorithm for Regular Expression Pattern Matching. Journal of the ACM, 39(2):430-448, April 1992.

317

Joseph Y. Halpern and Lenore D. Zuck. A Little Knowledge Goes a Long Way: Knowledge-Based Derivations and Correctness Proofs for a Family of Protocols. Journal of the ACM, 39(3):449-478, July 1992.

318

Lenwood S. Heath and Sorin Istrail. The Pagenumber of Genus g Graphs is O(g). Journal of the ACM, 39(3):479-501, July 1992.

319

A. Billionnet, M. C. Costa, and A. Sutter. An Efficient Algorithm for a Task Allocation Problem. Journal of the ACM, 39(3):502-518, July 1992.

320

David Eppstein, Zvi Galil, Faffaele Giancarlo, and Giuseppe F. Italiano. Sparse Dynamic Programming I: Linear Cost Functions. Journal of the ACM, 39(3):519-545, July 1992.

321

David Eppstein, Zvi Galil, Faffaele Giancarlo, and Giuseppe F. Italiano. Sparse Dynamic Programming II: Convex and Concave Cost Functions. Journal of the ACM, 39(3):546-567, July 1992.

322

Albert G. Greenberg and Neal Madras. How Fair Is Fair Queuing? Journal of the ACM, 39(3):568-598, July 1992.

323

M. Beaudry, P. McKenzie, and D. Thérien. The Membership Problem in Aperiodic Transformation Monoids. Journal of the ACM, 39(3):599-616, July 1992.

324

Amir M. Ben-Amram and Zvi Galil. On Pointers versus Addresses. Journal of the ACM, 39(3):617-648, July 1992.

325

William I. Gasarch and Carl H. Smith. Learning via Queries. Journal of the ACM, 39(3):649-674, July 1992.

326

Steven M. German and A. Prasad Sistla. Reasoning about Systems with Many Processes. Journal of the ACM, 39(3):675-735, July 1992.

327

Ran Raz and Avi Wigderson. Monotone Circuits for Matching Require Linear Depth. Journal of the ACM, 39(3):736-744, July 1992.

328

Allan Borodin, Nathan Linial, and Michael E. Saks. An Optimal On-line Algorithm for Metrical Task System. Journal of the ACM, 39(4):745-763, October 1992.

329

Amos Fiat, Moni Naor, Jeanette P. Schmidt, and Alan Siegel. Nonoblivious Hashing. Journal of the ACM, 39(4):764-782, October 1992.

330

Yishay Mansour and Baruch Schieber. The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels. Journal of the ACM, 39(4):783-799, October 1992.

331

Cynthia Dwork and Larry Stockmeyer. Finite State Verifiers I: The Power of Interaction. Journal of the ACM, 39(4):800-828, October 1992.

332

Cynthia Dwork and Larry Stockmeyer. Finite State Verifiers II: Zero Knowledge. Journal of the ACM, 39(4):829-858, October 1992.

333

Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. Journal of the ACM, 39(4):859-868, October 1992.

334

Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, October 1992.

335

A. Shen. IP = PSPACE: Simplified Proof. Journal of the ACM, 39(4):878-880, October 1992.

336

Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the Correctness of Orphan Management Algorithms. Journal of the ACM, 39(4):881-930, October 1992.

337

Oliver Collins, Sam Dolinar, Robert McEliece, and Fabrizio Pollara. A VLSI Decomposition of the deBruijn Graph. Journal of the ACM, 39(4):931-948, October 1992.

338

Saumya K. Debray. Efficient Dataflow Analysis of Logic Programs. Journal of the ACM, 39(4):949-984, October 1992.

339

M. B. Dillencourt, H. Samet, and M. Tamminen. Corrigenda: ``A General Approach to Connected Component Labeling for Arbitrary Image Representations''. Journal of the ACM, 39(4):985-986, October 1992.

340

Jean Gallier, Paliath Narendran, David Plaisted, Stan Raatz, and Wayne Snyder. An Algorithm for Finding Canonical Sets of Ground Rewrite Rules in Polynomial Time. Journal of the ACM, 40(1):1-16, January 1993.

341

Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly Secure Message Transmission. Journal of the ACM, 40(1):17-47, January 1993.

342

John D. Hobby. Generating Automatically Tuned Bitmaps from Outlines. Journal of the ACM, 40(1):48-94, January 1993.

343

Leonard Pitt and Manfred K. Warmuth. The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial. Journal of the ACM, 40(1):95-142, January 1993.

344

Robert Harper, Furio Honsell, and Gordon Plotkin. A Framework for Defining Logics. Journal of the ACM, 40(1):143-184, January 1993.

345

Dana Angluin, Lisa Hellerstein, and Marek Karpinski. Learning Read-Once Formulas with Queries. Journal of the ACM, 40(1):185-210, January 1993.

346

Nader H. Bshouty. On the Complexity of Functions for Random Access Machines. Journal of the ACM, 40(2):211-223, April 1993.

347

Andrea S. LaPaugh. Recontamination Does Not Help to Search a Graph. Journal of the ACM, 40(2):224-245, April 1993.

348

David McAllester and Robert Givan. Taxonomic Syntax for First Order Inference. Journal of the ACM, 40(2):246-283, April 1993.

349

David A. McAllester. Automatic Recognition of Tractability in Inference Relations. Journal of the ACM, 40(2):284-303, April 1993.

350

David M. Nicol. The Cost of Conservative Synchronization in Parallel Discrete Event Simulations. Journal of the ACM, 40(2):304-333, April 1993.

351

Gil Neiger and Sam Toueg. Simulating Synchronized Clocks and Common Knowledge in Distributed Systems. Journal of the ACM, 40(2):334-367, April 1993.

352

Thomas Lengauer and Egon Wanke. Efficient Decision Procedures for Graph Properties on Context-Free Graph Languages. Journal of the ACM, 40(2):368-393, April 1993.

353

Kin K. Leung. An Execution/Sleep Scheduling Policy for Serving an Additional Job in Priority Queueing Systems. Journal of the ACM, 40(2):394-417, April 1993.

354

Don Coppersmith, Peter Doyle, Prabhakar Raghavan, and Marc Snir. Random Walks on Weighted Graphs and Applications To On-line Algorithms. Journal of the ACM, 40(3):421-453, July 1993.

355

Howard J. Karloff and Prabhakar Raghavan. Randomized Algorithms and Pseudorandom Numbers. Journal of the ACM, 40(3):454-476, July 1993.

356

Franz Baader. Unification in Commutative Theories, Hilbert's Basis Theorem and Gröbner Bases. Journal of the ACM, 40(3):477-503, July 1993.

357

Neil V. Murray and Erik Rosenthal. Dissolution: Making Paths Vanish. Journal of the ACM, 40(3):504-535, July 1993.

358

C. A. Johnson. Factorization and Circuit in the Connection Method. Journal of the ACM, 40(3):536-557, July 1993.

359

Tie-Cheng Wang. Z-Module Reasoning: An Equality-Oriented Proving Method with Built-in Ring Axioms. Journal of the ACM, 40(3):558-606, July 1993.

360

Nathan Linial, Yishay Mansour, and Noam Nisan. Constant Depth Circuits, Fourier Transform and Learnability. Journal of the ACM, 40(3):607-620, July 1993.

361

Kurt Mehlhorn and Athanasios Tsakalidis. Dynamic Interpolation Search. Journal of the ACM, 40(3):621-634, July 1993.

362

Marc J. van Kreveld and Mark H. Overmars. Union-Copy Structures and Dynamic Segment Trees. Journal of the ACM, 40(3):635-652, July 1993.

363

J. C. M. Baeten, J. A. Bergstra, and J. W. Klop. Decidability of Bisimulation Equivalence for Processes Generating Context-Free Languages. Journal of the ACM, 40(3):653-682, July 1993.

364

Haim Gaifman, Harry Mairson, Yehoshua Sagiv, and Moshe Y. Vardi. Undecidable Optimization Problems for Database Logic Programs. Journal of the ACM, 40(3):683-713, July 1993.

365

Randolph Nelson and Donald Towsley. A Performance Evaluation of Several Priority Policies for Parallel Processing Systems. Journal of the ACM, 40(3):714-740, July 1993.

366

Sandeep Bhatt and Jin-Yi Cai. Taking Random Walks to Grow Trees in Hypercubes. Journal of the ACM, 40(3):741-764, July 1993.

367

Richard M. Karp and Yanjun Zhang. Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation. Journal of the ACM, 40(3):765-789, July 1993.

368

Edith Cohen and Nimrod Megiddo. Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Periodic Graphs. Journal of the ACM, 40(4):791-830, September 1993.

369

Philip S. Yu, Daniel M. Dias, and Stephen S. Lavenberg. On the Analytical Modeling of Database Concurrency Control. Journal of the ACM, 40(4):831-872, September 1993.

370

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic Snapshots of Shared Memory. Journal of the ACM, 40(4):873-890, September 1993.

371

Foto Afrati and Christos H. Papadimitriou. The Parallel Complexity of Simple Logic Programs. Journal of the ACM, 40(4):891-916, September 1993.

372

Joseph Y. Halpern and Mark R. Tuttle. Knowledge, Probability, and Adversaries. Journal of the ACM, 40(4):917-962, September 1993.

373

V. Wiktor Marek, Grigori F. Schwarz, and Miros aw Truszczyński. Modal Nonmonotonic Logics: Ranges, Characterization, Computation. Journal of the ACM, 40(4):963-990, September 1993.

374

E. G. Coffman, Jr. and M. R. Garey. Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling. Journal of the ACM, 40(5):991-1018, November 1993.

375

Zhi-Quan Luo and John N. Tsitsiklis. On the Communication Complexity of Distributed Algebraic Computation. Journal of the ACM, 40(5):1019-1047, November 1993.

376

Bruce Donald, Patrick Xavier, John Canny, and John Reif. Kinodynamic Motion Planning. Journal of the ACM, 40(5):1048-1066, November 1993.

377

Y. C. Tay. On the Optimality of Strategies for Multiple Joins. Journal of the ACM, 40(5):1067-1086, November 1993.

378

Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The Impossibility of Implementing Reliable Communication in the Face of Crashes. Journal of the ACM, 40(5):1087-1107, November 1993.

379

Martin Charles Golumbic and Ron Shamir. Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach. Journal of the ACM, 40(5):1108-1133, November 1993.

380

Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An Algebraic Theory of Graph Reduction. Journal of the ACM, 40(5):1134-1164, November 1993.

381

Jean Fonlupt and Armand Nachef. Dynamic Programming and the Graphical Traveling Salesman Problem. Journal of the ACM, 40(5):1165-1187, November 1993.

382

Alain Jean-Marie and Levent Gün. Parallel Queues with Resequencing. Journal of the ACM, 40(5):1188-1208, November 1993.

383

François Baccelli, Zhen Liu, and Don Towsley. Extremal Scheduling of Parallel Processing with and without Real-Time Constraints. Journal of the ACM, 40(5):1209-1237, November 1993.

384

Charles Knessl. On the Sojourn Time Distribution in a Finite Capacity Processor Shared Queue. Journal of the ACM, 40(5):1238-1301, November 1993.

385

Michael J. Fischer and Michael S. Paterson. Fishspear: A Priority Queue Algorithm. Journal of the ACM, 41(1):3-30, January 1994.

386

Daniel N. Rockmore. Efficient Computation of Fourier Inversion for Finite Groups. Journal of the ACM, 41(1):31-66, January 1994.

387

Michael Kearns and Leslie Valiant. Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. Journal of the ACM, 41(1):67-95, January 1994.

388

Pekka Orponen, Ker-I Ko, Uwe Schöning, and Osamu Watanabe. Instance Complexity. Journal of the ACM, 41(1):96-121, January 1994.

389

Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty. Journal of the ACM, 41(1):122-152, January 1994.

390

Brenda S. Baker. Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of the ACM, 41(1):153-180, January 1994.

391

Rajeev Alur and Thomas A. Henzinger. A Really Temporal Logic. Journal of the ACM, 41(1):181-204, January 1994.

392

Moshe Dubiner, Zvi Galil, and Edith Magen. Faster Tree Pattern Matching. Journal of the ACM, 41(2):205-213, March 1994.

393

Samir Khuller and Uzi Vishkin. Biconnectivity Approximations and Graph Carvings. Journal of the ACM, 41(2):214-235, March 1994.

394

Leo Bachmair and Nachum Dershowitz. Equational Inference, Canonical Proofs, and Proof Orderings. Journal of the ACM, 41(2):236-276, March 1994.

395

Karl Abrahamson, Andrew Adler, Lisa Higham, and David Kirkpatrick. Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings. Journal of the ACM, 41(2):277-310, March 1994.

396

Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda. The Elusive Atomic Register. Journal of the ACM, 41(2):311-339, March 1994.

397

Ronald Fagin and Joseph Y. Halpern. Reasoning about Knowledge and Probability. Journal of the ACM, 41(2):340-367, March 1994.

398

A. J. Kfoury, J. Tiuryn, and P. Urzyczyn. An Analysis of ML Typability. Journal of the ACM, 41(2):368-398, March 1994.

399

Michael Cosnard and El Mostafa Daoudi. Optimal Algorithms for Parallel Givens Factorization on a Coarse-Grained PRAM. Journal of the ACM, 41(2):399-421, March 1994.

400

Noga Alon and Nimrod Megiddo. Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. Journal of the ACM, 41(2):422-434, March 1994.

401

Peter B. Ladkin and Roger D. Maddux. On Binary Constraint Problems. Journal of the ACM, 41(3):435-469, May 1994.

402

Avrim Blum. New Approximation Algorithms for Graph Coloring. Journal of the ACM, 41(3):470-516, May 1994.

403

Doron Drusinsky and David Harel. On the Power of Bounded Concurrency I: Finite Automata. Journal of the ACM, 41(3):517-539, May 1994.

404

Tirza Hirst and David Harel. On the Power of Bounded Concurrency II: Pushdown Automata. Journal of the ACM, 41(3):540-554, May 1994.

405

Ronald L. Rivest and Robert E. Schapire. Diversity-Based Inference of Finite Automata. Journal of the ACM, 41(3):555-589, May 1994.

406

Wray L. Buntine and Hans-Jürgen Bürckert. On Solving Equations and Disequations. Journal of the ACM, 41(4):591-629, July 1994.

407

Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear Approximation of Shortest Superstrings. Journal of the ACM, 41(4):630-647, July 1994.

408

Adrian E. Conway, Eugene Pinsky, and Srinivasan Tridandapani. Efficient Decomposition Methods for the Analysis of Multi-Facility Blocking Models. Journal of the ACM, 41(4):648-675, July 1994.

409

John C. S. Lui and Richard R. Muntz. Computing Bounds on Steady State Availability of Repairable Computer Systems. Journal of the ACM, 41(4):676-707, July 1994.

410

Timothy C. Bell and Ian H. Witten. The Relationship between Greedy Parsing and Symbolwise Text Compression. Journal of the ACM, 41(4):708-724, July 1994.

411

Hagit Attiya, Nancy Lynch, and Nir Shavit. Are Wait-Free Algorithms Fast? Journal of the ACM, 41(4):725-763, July 1994.

412

John Reif and Micha Sharir. Motion Planning in the Presence of Moving Obstacles. Journal of the ACM, 41(4):764-790, July 1994.

413

Shaodi Gao and Michael Kaufmann. Channel Routing of Multiterminal Nets. Journal of the ACM, 41(4):791-818, July 1994.

414

Peter K. Rathmann, Marianne Winslett, and Mark Manasse. Circumscription with Homomorphisms: Solving the Equality and Counterexample Problems. Journal of the ACM, 41(5):819-873, September 1994.

415

Christopher J. Glass and Lionel M. Ni. The Turn Model for Adaptive Routing. Journal of the ACM, 41(5):874-902, September 1994.

416

Yves Dallery, Zhen Liu, and Don Towsley. Equivalence, Reversibility, Symmetry and Concavity Properties in Fork-Join Queuing Networks with Blocking. Journal of the ACM, 41(5):903-942, September 1994.

417

James R. Driscoll, Daniel D. K. Sleator, and Robert E. Tarjan. Fully Persistent Lists with Catenation. Journal of the ACM, 41(5):943-959, September 1994.

418

Carsten Lund and Mihalis Yannakakis. On the Hardness of Approximating Minimization Problems. Journal of the ACM, 41(5):960-981, September 1994.

419

James A. Storer and John H. Reif. Shortest Paths in the Plane with Polygonal Obstacles. Journal of the ACM, 41(5):982-1012, September 1994.

420

John H. Reif and James A. Storer. A Single-Exponential Upper Bounds for Finding Shortest Paths in Three Dimensions. Journal of the ACM, 41(5):1013-1019, September 1994.

421

James Aspnes, Maurice Herlihy, and Nir Shavit. Counting Networks. Journal of the ACM, 41(5):1020-1048, September 1994.

422

Mikhail J. Atallah, Michael T. Goodrich, and S. Rao Kosaraju. Parallel Algorithms for Evaluating Sequences of Set-Manipulation Operations. Journal of the ACM, 41(6):1049-1088, November 1994.

423

Tal Rabin. Robust Sharing of Secrets when the Dealer Is Honest or Cheating. Journal of the ACM, 41(6):1089-1109, November 1994.

424

Keith W. Ross, Danny H. K. Tsang, and Jie Wang. Monte Carlo Summation and Integration Applied to Multiclass Queuing Networks. Journal of the ACM, 41(6):1110-1135, November 1994.

425

Richard M. Karp. Probabilistic Recurrence Relations. Journal of the ACM, 41(6):1136-1150, November 1994.

426

Jeffrey F. Naughton and Raghu Ramakrishnan. How to Forget the Past without Repeating It. Journal of the ACM, 41(6):1151-1177, November 1994.

427

Colin Bell, Anil Nerode, Raymond T. Ng, and V. S. Subrahmanian. Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases. Journal of the ACM, 41(6):1178-1215, November 1994.

428

Kenneth A. Ross. Modular Stratification and Magic Sets for Datalog Programs with Negation. Journal of the ACM, 41(6):1216-1266, November 1994.

429

Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Nancy Lynch, Yishay Mansour, Dai-Wei Wang, and Lenore Zuck. Reliable Communication Over Unreliable Channels. Journal of the ACM, 41(6):1267-1297, November 1994.

430

Michael Kearns, Ming Li, and Leslie Valiant. Learning Boolean Formulas. Journal of the ACM, 41(6):1298-1328, November 1994.

431

Rajeev Motwani. Average-Case Analysis of Algorithms for Matchings and Related Problems. Journal of the ACM, 41(6):1329-1356, November 1994.

432

Thomas Eiter and Georg Gottlob. The Complexity of Logic-Based Abduction. Journal of the ACM, 42(1):3-42, January 1995.

433

Bernhard Nebel and Hans-Jürgen Bürckert. Reasoning About Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra. Journal of the ACM, 42(1):43-66, January 1995.

434

Paul B. Callahan and S. Rao Kosaraju. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. Journal of the ACM, 42(1):67-90, January 1995.

435

Andrew A. Chien and Jae H. Kim. Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors. Journal of the ACM, 42(1):91-123, January 1995.

436

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing Memory Robustly in Message-Passing Systems. Journal of the ACM, 42(1):124-142, January 1995.

437

Danny Dolev, Joseph Y. Halpern, Barbara Simons, and Ray Strong. Dynamic Fault-Tolerant Clock Synchronization. Journal of the ACM, 42(1):143-185, January 1995.

438

S. Haldar and K. Vidyasankar. Constructing 1-Writer Multireader Multivalued Atomic Variable from Regular Variables. Journal of the ACM, 42(1):186-203, January 1995.

439

C. S. Chang and R. Nelson. Bounds on the Speedup and Efficiency of Partial Synchronization in Parallel Processing Systems. Journal of the ACM, 42(1):204-231, January 1995.

440

Bard Bloom, Sorin Istrail, and Albert R. Meyer. Bisimulation Can't Be Traced. Journal of the ACM, 42(1):232-268, January 1995.

441

Manuel Blum and Sampath Kannan. Designing Programs that Check Their Work. Journal of the ACM, 42(1):269-291, January 1995.

442

Fangzhen Lin and Yoav Shoham. Provably Correct Theories of Action. Journal of the ACM, 42(2):293-320, March 1995.

443

David R. Karger, Philip N. Klein, and Robert E. Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. Journal of the ACM, 42(2):321-328, March 1995.

444

Ke Wang, Weining Zhang, and Siu-Cheung Chau. Decomposition of Magic Rewriting. Journal of the ACM, 42(2):329-381, March 1995.

445

John N. Tsitsiklis and George D. Stamoulis. On the Average Communication Complexity of Asynchronous Distributed Algorithms. Journal of the ACM, 42(2):382-400, March 1995.

446

Stuart A. Kurtz, Stephen R. Mahaney, and James S. Royer. The Isomorphism Conjecture Fails Relative to a Random Oracle. Journal of the ACM, 42(2):401-420, March 1995.

447

Georg Gottlob. NP Trees and Carnap's Modal Logic. Journal of the ACM, 42(2):421-457, March 1995.

448

Rocco De Nicola and Frits Vaandrager. Three Logics for Branching Bisimulation. Journal of the ACM, 42(2):458-487, March 1995.

449

Kenneth L. Clarkson. Las Vegas Algorithms for Linear and Integer Programming When the Dimension is Small. Journal of the ACM, 42(2):488-499, March 1995.

450

Bonnie Berger, Martin Brady, Donna Brown, and Tom Leighton. Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing. Journal of the ACM, 42(2):500-542, March 1995.

451

Peter van Beek and Rina Dechter. On the Minimality and Global Consistency of Row-Convex Constraint Networks. Journal of the ACM, 42(3):543-561, May 1995.

452

Kevin J. Compton and Chinya Ravishankar. Expected Deadlock Time in a Multiprocessing System. Journal of the ACM, 42(3):562-583, May 1995.

453

Yannis A. Korilis and Aurel A. Lazar. On the Existence of Equilibria in Noncooperative Optimal Flow Control. Journal of the ACM, 42(3):584-613, May 1995.

454

Paul Bay and Gianfranco Bilardi. Deterministic On-Line Routing on Area-Universal Networks. Journal of the ACM, 42(3):614-640, May 1995.

455

Alexander Birman, H. Richard Gail, Sidney L. Hantler, Zvi Rosberg, and Moshe Sidi. An Optimal Service Policy for Buffer Systems. Journal of the ACM, 42(3):641-657, May 1995.

456

P. W. O'Hearn and R. D. Tennent. Parametricity and Local Variables. Journal of the ACM, 42(3):658-709, May 1995.

457

Georg Gottlob. Translating Default Logic into Standard Autoepistemic Logic. Journal of the ACM, 42(4):711-740, July 1995.

458

Michael Kifer, Georg Lausen, and James Wu. Logical Foundations of Object-Oriented and Frame-Based Languages. Journal of the ACM, 42(4):741-843, July 1995.

459

Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, July 1995.

460

Costas Courcoubetis and Mihalis Yannakakis. The Complexity of Probabilistic Verification. Journal of the ACM, 42(4):857-907, July 1995.

461

Zvi Galil. A Constant-Time Optimal Parallel String-Matching Algorithm. Journal of the ACM, 42(4):908-918, July 1995.

462

Mark H. Nodine and Jeffrey Scott Vitter. Greed Sort: Optimal Deterministic Sorting on Parallel Disks. Journal of the ACM, 42(4):919-933, July 1995.

463

Gagan L. Choudhury, Kin K. Leung, and Ward Whitt. Calculating Normalization Constants of Closed Queueing Networks by Numerically Inverting Their Generating Functions. Journal of the ACM, 42(5):935-970, September 1995.

464

Elias Koutsoupias and Christos H. Papadimitriou. On the k-Server Conjecture. Journal of the ACM, 42(5):971-983, September 1995.

465

Rakesh M. Verma. A Theory of Using History for Equational Systems with Applications. Journal of the ACM, 42(5):984-1020, September 1995.

466

Baruch Awerbuch and David Peleg. Online Tracking of Mobile Users. Journal of the ACM, 42(5):1021-1058, September 1995.

467

Ewan D. Tempero and Richard E. Ladner. Recoverable Sequence Transmission Protocols. Journal of the ACM, 42(5):1059-1090, September 1995.

468

Nabil Kahale. Eigenvalues and Expansion of Regular Graphs. Journal of the ACM, 42(5):1091-1106, September 1995.

469

Michel Conforti and Gérard Cornuéjols. A Class of Logic Problems Solvable by Linear Programming. Journal of the ACM, 42(5):1107-1113, September 1995.

470

Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42(6):1115-1145, November 1995.

471

Rūsiņš Freivalds, Efim Kinber, and Carl H. Smith. On the Impact of Forgetting on Learning Machines. Journal of the ACM, 42(6):1146-1168, November 1995.

472

Joan Boyar, Gilles Brassard, and René Peralta. Subquadratic Zero-Knowledge. Journal of the ACM, 42(6):1169-1193, November 1995.

473

J. A. Bergstra and J. V. Tucker. Equational Specifications, Complete Term Rewriting Systems, and Computable and Semicomputable Algebras. Journal of the ACM, 42(6):1194-1230, November 1995.

474

Yehuda Afek, David S. Greenberg, Michael Merritt, and Gadi Taubenfeld. Computing with Faulty Shared Ojects. Journal of the ACM, 42(6):1231-1274, November 1995.

475

Y. Toyama, Jan Willem Klop, and H. P. Barendregt. Termination for Direct Sums of Left-Linear Complete Term Rewriting Systems. Journal of the ACM, 42(6):1275-1304, November 1995.

476

Yehuda Afek, Baruch Awerbuch, Serge Plotkin, and Michael Saks. Local Management of a Global Resource in a Communication Network. Journal of the ACM, 43(1):1-19, January 1996.

477

Weidong Chen and David S. Warren. Tabled Evaluation with Delaying for General Logic Programs. Journal of the ACM, 43(1):20-74, January 1996.

478

Yuh-Jzer Joung and Scott A. Smolka. A Comprehensive Study of the Complexity of Multiparty Interaction. Journal of the ACM, 43(1):75-115, January 1996.

479

Rajeev Alur, Tomás Feder, and Thomas A. Henzinger. The Benefits of Relaxing Punctuality. Journal of the ACM, 43(1):116-146, January 1996.

480

Peter Bro Miltersen, Mike Paterson, and Jun Tarui. The Asymptotic Complexity of Merging Networks. Journal of the ACM, 43(1):147-165, January 1996.

481

Robert S. Boyer and Yuan Yu. Automated Proofs of Object Code for a Widely Used Microprocessor. Journal of the ACM, 43(1):166-192, January 1996.

482

Bart Selman and Henry Kautz. Knowledge Compilation and Theory Approximation. Journal of the ACM, 43(2):193-224, March 1996.

483

Tushar Deepak Chandra and Sam Toueg. Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM, 43(2):225-267, March 1996.

484

Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive Proofs and the Hardness of Approximating Cliques. Journal of the ACM, 43(2):268-292, March 1996.

485

Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, F. Thomson Leighton, Bojana Obrenić, Arnold L. Rosenberg, and Eric J. Schwabe. Optimal Emulations by Butterfly-Like Networks. Journal of the ACM, 43(2):293-330, March 1996.

486

Michael T. Goodrich and S. Rao Kosaraju. Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation. Journal of the ACM, 43(2):331-361, March 1996.

487

Pierre-Louis Curien, Thérèse Hardin, and Jean-Jacques Lévy. Confluence Properties of Weak and Strong Calculi of Explicit Substitutions. Journal of the ACM, 43(2):362-397, March 1996.

488

Eugene Santos, Jr. On Linear Potential Functions for Approximating Bayesian Computations. Journal of the ACM, 43(3):399-430, May 1996.

489

Oded Goldreich and Rafail Ostrovsky. Software Protection and Simulation on Oblivious RAMs. Journal of the ACM, 43(3):431-473, May 1996.

490

Sherry Marcus and V. S. Subrahmanian. Foundations of Multimedia Database Systems. Journal of the ACM, 43(3):474-523, May 1996.

491

Mark-Jan Nederhof and Eberhard Bertsch. Linear-Time Suffix Parsing for Deterministic Languages. Journal of the ACM, 43(3):524-554, May 1996.

492

Rob J. van Glabbeek and W. Peter Weijland. Branching Time and Abstraction in Bisimulation Semantics. Journal of the ACM, 43(3):555-600, May 1996.

493

David R. Karger and Clifford Stein. A New Approach to the Minimum Cut Problem. Journal of the ACM, 43(4):601-640, July 1996.

494

William C. Cheng and Richard R. Muntz. Bounding Errors Introduced by Clustering of Customers in Closed Product-Form Queueing Networks. Journal of the ACM, 43(4):641-669, July 1996.

495

Antoni Kościelski and Leszek Pacholski. Complexity of Makanin's Algorithm. Journal of the ACM, 43(4):670-684, July 1996.

496

Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The Weakest Failure Detector for Solving Consensus. Journal of the ACM, 43(4):685-722, July 1996.

497

Ming Li, John Tromp, and Paul M. B. Vitányi. How to Share Concurrent Wait-Free Variables. Journal of the ACM, 43(4):723-746, July 1996.

498

Nader H. Bshouty and Christino Tamon. On the Fourier Spectrum of Monotone Functions. Journal of the ACM, 43(4):747-770, July 1996.

499

Jeffrey Scott Vitter and P. Krishnan. Optimal Prefetching via Data Compression. Journal of the ACM, 43(5):771-793, September 1996.

500

Costas Busch and Marios Mavronicolas. A Combinatorial Treatment of Balancing Networks. Journal of the ACM, 43(5):794-839, September 1996.

501

Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, and Dawn Wilkins. How Many Queries are Needed to Learn? Journal of the ACM, 43(5):840-862, September 1996.

502

Roland Bol and Jan Friso Groote. The Meaning of Negative Premises in Transition System Specifications. Journal of the ACM, 43(5):863-914, September 1996.