Journal of the ACM, Volume 38, 1991

Volume 38, Number 1, January 1991

Martin E. Dyer, Alan M. Frieze, Ravi Kannan:
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. 1-17
Joseph S. B. Mitchell, Christos H. Papadimitriou:
The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision. 18-73
Ketan Mulmuley:
A Fast Planar Partition Algorithm, II. 74-103
Dan E. Willard:
Optimal Sample Cost Residues for Differential Database Batch Query Problems. 104-119
Yehoshua Sagiv:
Evaluation of Queries in Independent Database Schemes. 120-161
Greg N. Frederickson:
Planar Graph Decomposition and All Pairs Shortest Paths. 162-204
V. Chandru, John N. Hooker:
Extended Horn Sets In Propositional Logic. 205-221
Gloria Kissin:
Upper and Lower Bounds on Switching Energy in VLSI. 222-254

Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis:
Modularity of Cycles and Paths in Graphs. 255-274
David P. Dobkin, Subhash Suri:
Maintenance of Geometric Extrema. 275-298
Randal E. Bryant:
A Methodology for Hardware Verification Based on Logic Simulation. 299-328
Yannis E. Ioannidis, Eugene Wong:
Towards an Algebraic Theory of Recursion. 329-381
Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi:
A Model-Theoretic Analysis of Knowledge. 382-428
Nicholas Bambos, Jean C. Walrand:
On Stability and Performance of Parallel Processing Systems. 429-452
Yishay Mansour, Baruch Schieber, Prasoon Tiwari:
A Lower Bound for Integer Greatest Common Divisor Computations. 453-471
Anne Condon:
Space-Bounded Probabilistic Game Automata. 472-494
Noga Alon, A. K. Dewdney, Teunis J. Ott:
Efficient Simulation of Finite Automata by Neural Nets. 495-514

Frank Thomson Leighton: Letter from the Editor. 515-515
Mikhail J. Atallah, Danny Z. Chen, Hubert Wagener:
An Optimal Parallel Algorithm for the Visibility of a Simple Polygon from a Point. 516-533
Tomasz Imielinski:
Abstraction in Query Processing. 534-558
Jieh Hsiang, Michaël Rusinowitch:
Proving Refutational Completeness of Theorem-Proving Strategies: The Transfinite Semantic Tree Method. 559-587
V. Wiktor Marek, Miroslaw Truszczynski:
Autoepistemic Logic. 588-619
Allen Van Gelder, Kenneth A. Ross, John S. Schlipf:
The Well-Founded Semantics for General Logic Programs. 620-650, (preliminary version: PODS 1988: 221-230)
Maxime Crochemore, Dominique Perrin:
Two-Way String Matching. 651-675
Keith W. Ross, David D. Yao:
Optimal Load Balancing and Scheduling in a Distributed Computer System. 676-690
Oded Goldreich, Silvio Micali, Avi Wigderson:
Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. 691-729
Cüneyt M. Özveren, Alan S. Willsky, Panos J. Antsaklis:
Stability and Stabilizability of Discrete Event Dynamic Systems. 730-752
Jacobo Torán:
Complexity Classes Defined by Counting Quantifiers. 753-774

Bradley S. Stewart, Chelsea C. White III:
Multiobjective A*. 775-814
Harold N. Gabow, Robert Endre Tarjan:
Faster Scaling Algorithms for General Graph-Matching Problems. 815-853
Edward P. F. Chan, Héctor J. Hernández:
Independence-Reducible Database Schemes. 854-886
Stephen L. Bloom, Zoltán Ésik:
Floyd-Hoare Logic in Iteration Theories. 887-934
Joseph Y. Halpern, Yoav Shoham:
A Propositional Modal Logic of Time Intervals. 935-962
Michael L. Tiomkin, Michael Kaminski:
Nonmonotonic Default Modal Logics. 963-984
Egon Balas, Donald L. Miller, Joseph F. Pekny, Paolo Toth:
A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem. 985-1004
Paul Glasserman:
Structural Conditions for Perturbation Analysis of Queuing Systems. 1005-1025
Bonnie Berger, John Rompel:
Simulating (log c n)-Wise Independence in NC. 1026-1046

Last update Wed May 22 17:52:41 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page