%%% ====================================================================
%%%  BibTeX-file{
%%%     filename  = "JACM.bib",
%%%     version   = "3.02",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/jacm.bib",
%%%     date      = "15 September 1998",
%%%     time      = "19:43:24 EDT",
%%%     author    = "David M. Jones",
%%%     address   = "MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "02191 4738 11538 122340",
%%%     email     = "jacm at theory.lcs.mit.edu",
%%%     codetable = "ISO/ASCII",
%%%     keywords  = "computer science, bibliography, BibTeX",
%%%     supported = "yes",
%%%     docstring = "The checksum field above contains a CRC-16
%%%                  checksum as the first value, followed by the
%%%                  equivalent of the standard UNIX wc (word count)
%%%                  utility output of lines, words, and characters.
%%%                  This is produced by Robert Solovay's checksum
%%%                  utility.",
%%%  }
%%% ====================================================================

                          JOURNAL OF THE ACM
                      January 1991 -- July 1995
                            Volumes 38--43

This is BibTeX bibliography containing all papers published in the
Journal of the ACM since January 1992.  There are undoubtably numerous
small errors left in it.  Please report any errors you find to jacm at
theory.lcs.mit.edu.  For documentation on using this file, see Chapter
13 of "The LaTeX Companion" by Michel Goossens and Frank Mittelbach
and Alexander Samarin, Addison-Wesley, 1993, or Section 4.3 and
Appendix B of "LaTeX: A Document Preparation System" by Leslie
Lamport.

NOTE: This file will only work under BibTeX version 0.99a or later, as
it makes use of the string concatenation feature which was introduced
in that release.

@string{jacm={Journal of the ACM}}

                             January 1991
                         Volume 38, Number 1

@Article{DyerFK91,
title={A Random Polynomial-Time Algorithm for Approximating the Volume
of Convex Bodies},
author={Martin Dyer and Alan Frieze and Ravi Kannan},
area={Computational Geometry},
pages={1--17},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Algorithms},
keywords={Convex sets, random walks, sampling, volume},
cr-categories={F.2.2 [geometric problems and computations]; G.3
[probabilistic algorithms (including Monte Carlo)]}
}

@Article{MitchellP91,
title={The Weighted Region Problem: Finding Shortest Paths Through a
Weighted Planar Subdivision},
author={Joseph S. B. Mitchell and Christos H. Papadimitriou},
area={Computational Geometry},
pages={18--73},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
cr-categories={F.2.2 [geometrical problems and computations \and
routing and layout]; G.1.6 [nonlinear programming]; G.2.2 [path and
circuit problems]; I.2.8}
}

@Article{Mulmuley91,
title={A Fast Planar Partition Algorithm, {II}},
author={Ketan Mulmuley},
area={Computational Geometry},
pages={74--103},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Algorithms, Theory},
keywords={Computational complexity, computational geometry, hidden
surface removal, randomized geometric algorithms, planar subdivision},
cr-categories={F.2.2 [computations on discrete structures \and
geometrical problems and computations]; G.2.1 [combinatorical
algorithms]; I.3.5 [geometric algorithms, languages and systems];
I.3.7 [visible line/surface algorithms]}
}

@Article{Willard91,
title={Optimal Sample Cost Residues for Differential Database Batch
Query Problems},
author={Dan E. Willard},
area={Data Structure and Algorithms},
pages={104--119},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Measurements, Performance},
keywords={Databases, sampling},
cr-categories={E.5; H.3.2; H.3.3}
}

@Article{Sagiv91,
title={Evaluation of Queries in Independent Database Schemes},
author={Yehoshua Sagiv},
area={Database Theory},
pages={120--161},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Algorithms, Design, Theory},
keywords={Chase, expanded cover, extension join, functional
dependency, independent database scheme, join dependency, lossless
join, null value, query evaluation, relational algebra, relational
database, representative instance, restricted projection, tableau,
union of tableaux},
cr-categories={H.2.1 [normal forms \and scheme and subschema]; H.2.4
[query processing]; F.4.1 [model theory]}
}

@Article{Frederickson91,
title={Planar Graph Decomposition and All Pairs Shortest Paths},
author={Greg N. Frederickson},
area={Graph Theory},
pages={162--204},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Algorithms, Theory},
keywords={All pairs shortest paths, approximation algorithm, compact
routing table, graph embedding, NP-completeness, outerplanar graph,
planar graph, succinct encoding},
cr-categories={E.1 [graphs]; F.2.2 [computations on discrete
structures]; G.2.2 [graph algorithms \and network problems]}
}

@Article{ChandruH91,
title={Extended {Horn} Sets in Propositional Logic},
author={V. Chandru and J. N. Hooker},
area={Logic Programming},
pages={205--221},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Algorithms, Theory},
keywords={Horn clauses, propositional logic},
cr-categories={F.4.1 [computational logic \and mechanical theorem
proving]; G.1.6 [integer programming]; H.2.1; I.2.3 [deduction \and
resolution]}
}

@Article{Kissin91,
title={Upper and Lower Bounds on Switching Energy in {VLSI}},
author={Gloria Kissin},
area={Theory of Computation},
pages={222--254},
journal=jacm,
month=jan,
year=1991,
volume=38,
number=1,
general-terms={Algorithms, Design, Measurement, Performance, Theory},
keywords={Addition, AND function, average-case analysis, CID VLSI
circuit, circuit scheme, compare functions, embedding, energy
consumption, energy-efficient, layout, multiswitch models,
1-switchable functions, OR function, parity function, switching
energy, uniswitch energy, upper and lower bounds, USM},
cr-categories={B.2.1 [parallel]; B.2.2 [worst-case and average-case
analysis]; B.6.1 [combinatorial logic \and parallel circuits]; B.7.1
[VLSI]; B.7.2 [layout]; F.1.1 [circuits]; F.1.2 [parallelism]; F.2.2
[computations on discrete structures \and routing and layout]; F.2.3}
}

                              April 1991
                         Volume 38, Number 2

@Article{ArkinPY91,
title={Modularity of Cycles and Paths in Graphs},
author={E. M. Arkin and C. H. Papadimitriou and M. Yannakakis},
area={Combinatorics and Graph Theory},
pages={255--274},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Algorithms, Theory},
keywords={Algorithms, cycles and paths, graphs, modularity},
cr-categories={F.2.m; G.2.2 [network problems \and path and circuit
problems]}
}

@Article{DobkinS91,
title={Maintenance of Geometric Extrema},
author={David Dobkin and Subhash Suri},
area={Computational Geometry},
pages={275--298},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Algorithms, Theory},
keywords={Decomposability, dynamization, geometric algorithms,
semi-online model, Voronoi diagram},
cr-categories={F.2.2 [geometric problems and computations]}
}

@Article{Bryant91,
title={A Methodology for Hardware Verification Based on Logic
Simulation},
author={Randal E. Bryant},
area={Computer Systems},
pages={299--328},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Theory, Verfication},
keywords={Hardware verification, logic simulation, ternary
simulation},
cr-categories={B.6.3 [simulation \and switching theory \and
verification]}
}

@Article{IoannidisW91,
title={Towards an Algebraic Theory of Recursion},
author={Yannis E. Ioannidis and Eugene Wong},
area={Database Theory},
pages={329--381},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
other-refs={POPL::AhoU79},
general-terms={},
keywords={},
cr-categories={D.3.2 [nonprocedural languages]; F.3.2 [algebraic
approaches to semantics]; F.4.1 [logic programming]; H.2.3 [query
languages]; I.1.3 [nonprocedural languages \and special-purpose
algebraic systems]; I.2.3 [logic programming]}
}

@Article{FaginHV91,
title={A Model-Theoretic Analysis of Knowledge},
author={Ronald Fagin and Joseph Y. Halpern and Moshe Y. Vardi},
area={Distributed Computing},
pages={382--428},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Theory},
keywords={Common knowledge, distributed systems, epistemology,
knowledge, knowledge structures, Kripke structure, modal logic,
possible worlds, reasoning about knowledge},
cr-categories={F.4.1 [model theory]; I.2.4 [representation languages]}
}

@Article{BambosW91,
title={On Stability and Performance of Parallel Processing Systems},
author={Nicholas Bambos and Jean Walrand},
area={System Modeling and Analysis},
pages={429--452},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Design, Performance, Theory},
keywords={Database concurrency control, parallel processing, queuing
networks, queuing theory, stability theory, subadditive ergodic
theory},
cr-categories={C.1.2 [parallel processors]; C.4 [modeling techniques];
D.4.1 [concurrency]; D.4.8 [queuing theory \and stochastic analysis];
H.2.4 [concurrency]}
}

@Article{MansourST91,
title={A Lower Bound for Integer Greatest Common Divisor
Computations},
author={Yishay Mansour and Baruch Schieber and Prasoon Tiwari},
area={Theory of Computation},
pages={453--471},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Algorithms},
keywords={Floor operation, greatest common divisor, lower bound, mod
operation, truncation},
cr-categories={F.2.1 [number-theoretic computations]}
}

@Article{Condon91,
title={Space-Bounded Probabilistic Game Automata},
author={Anne Condon},
area={Theory of Computation},
pages={472--494},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Theory},
keywords={Arthur-Merlin games, interactive proof systems,
probabilistic game automata},
cr-categories={F.1.1 [automata \and bounded-action devices]; F.1.2
[alternation and nondeterminism \and probabilistic computation]; F.1.3
[relations among complexity classes]}
}

@Article{AlonDO91,
title={Efficient Simulation of Finite Automata by Neural Nets},
author={Noga Alon and A. K. Dewdney and Teunis J. Ott},
area={Theory of Computation},
pages={495--514},
journal=jacm,
month=apr,
year=1991,
volume=38,
number=2,
general-terms={Neural nets, Finite automata},
keywords={Mealy Machines},
cr-categories={F.1.1 [automata \and relations between models]}
}

                              July 1991
                         Volume 38, Number 3

@Article{Leighton91,
title={Letter From the Editor},
author={Tom Leighton},
pages={515},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3
}

@Article{AtallahCW91,
title={An Optimal Parallel Algorithm for the Visibility of a Simple
Polygon from a Point},
author={Mikhail J. Atallah and Danny Z. Chen and Hubert Wagener},
area={Computational Geometry},
pages={516--533},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Algorithms, Theory},
keywords={Computational geometry, intersections of polygonal chains,
parallel computational complexity, simple polygons, visible regions},
cr-categories={F.2.2 [computations on discrete structures \and
geometrical problems and computations]; I.3.5 [geometrical
algorithms]}
}

@Article{Imielinski91,
title={Abstraction in Query Processing},
author={Tomasz Imielinski},
area={Database Theory},
pages={534--558},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Management, Theory},
keywords={Chase procedure, data dependencies, incomplete information},
cr-categories={H.2.4 [query processing]; I.2.3 [answer extraction \and
deduction]; I.2.4 [knowledge representation \andfoundations and
methods \and predicate calculus]}
}

@Article{HsiangR91,
title={Proving Refutational Completeness of Theorem-Proving
Strategies: The Transfinite Semantic Tree Method},
author={Jieh Hsiang and Micha{\"e}l Rusinowitch},
area={Logic},
pages={559--587},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Theory},
keywords={Refutational Theorem Proving Strategies, Transfinite
Ordinals, Transfinite Semantic Trees, Resolution, Complete
simplification orderings, completeness, first-order logic with
equality, functional reflexive axioms, paramodulation, resolution,
transfinite ordinals, transfinite semantic trees},
cr-categories={F.4.1 [mechanical theorem proving \and proof theory];
I.2.3 [deduction \and resolution]}
}

@Article{MarekT91,
title={Autoepistemic Logic},
author={Wiktor Marek and Miroslaw Truszczynski},
area={Logic},
pages={588--619},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Theory},
keywords={Autoepistemic logic, expansion, logic programming,
NP-completeness, stratification},
cr-categories={F.4.1 [mechanical theorem proving \and logic
programming]; I.2.3 [nonmonotonic reasoning and belief revision]}
}

@Article{GelderRS91,
title={The Well-Founded Semantics for General Logic Programs},
author={Allen Van Gelder and Kenneth A. Ross and John S. Schlipf},
area={Logic Programming},
pages={620--650},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
cr-categories={D.3.1 [semantics]; F.4.1 [logic]}
}

@Article{CrochemoreP91,
title={Two-Way String-Matching},
author={Maxime Crochemore and Dominique Perrin},
area={String Processing},
pages={651--675},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Algorithms, Design, Theory},
keywords={Analysis of Algorithms, combinatorial algorithms, pattern
matching, text processing},
cr-categories={D.1.0; F.2.2; G.2.2; I.5; I.7}
}

@Article{RossY91,
title={Optimal Load Balancing and Scheduling in a Distributed Computer
System},
author={Keith W. Ross and David D. Yao},
area={System Modeling and Analysis},
pages={676--690},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Algorithms, Management, Performance},
keywords={Load balancing, queuing theory, scheduling},
cr-categories={C.2.1; C.4 [modeling techniques]}
}

@Article{GoldreichMW91,
title={Proofs that Yield Nothing But Their Validity or All Languages
in {NP} Have Zero-Knowledge Proof Systems},
author={Oded Goldreich and Silvio Micali and Avi Wigderson},
area={Theory of Computation},
pages={691--729},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
cr-categories={C.2.0 [data]}
}

@Article{OzverenWA91,
title={Stability and Stabilizability of Discrete Event Dynamic
Systems},
author={C{\"u}neyt M. {\"O}zveren and Alan S. Willsky and Panos J.
Antsaklis},
area={Theory of Computation},
pages={730--752},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Algorithms, Design, Languages, Reliability, Theory},
keywords={Reliability, self-stabilizing systems, stability,
stabilizability, state feedback},
cr-categories={F.2.2 [computations on discrete structures \and
sequencing and scheduling]; F.4.3 [algebraic language theory \and
classes defined by grammars or automata]; G.2.2 [graph algorithms];
G.4 [algorithm analysis \and reliability and robustness]; H.2.8; J.7
[command and control \and process control]}
}

@Article{Toran91,
title={Complexity Classes Defined by Counting Quantifiers},
author={Jacobo Tor{\'a}n},
area={Theory of Computation},
pages={753--774},
journal=jacm,
month=jul,
year=1991,
volume=38,
number=3,
general-terms={Theory},
keywords={Counting complexity classes},
cr-categories={F.1.2 [relativized computation]; F.1.3 [complexity
hierarchies \and relations among complexity classes]}
}

                             October 1991
                         Volume 38, Number 4

@Article{StewartW91,
title={Multiobjective {$A*$}},
author={Bradley S. Stewart and White, III, Chelsea C.},
area={Artificial Intelligence},
pages={775--814},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Theory},
keywords={$A*$ multiobjective decisionmaking},
cr-categories={F.2.2 [computations on discrete structures \and routing
and layout \and sorting and searching]; G.2.1 [combinatorial
algorithms]; G.2.2 [graph algorithms \and network problems \and path
and dynamic programming \and graph and tree search strategies \and
heuristic methods]}
}

@Article{GabowT91,
title={Faster Scaling Algorithms for General Graph-Matching Problems},
author={Harold N. Gabow and Robert E. Tarjan},
area={Combinatorics and Graph Theory},
pages={815--853},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Algorithms, Design, Theory},
keywords={Augmenting path, blossom, matching, network optimization,
scaling},
cr-categories={F.2.2 [computations on discrete structures]; G.2.2
[graph algorithms \and networks of problems]}
}

@Article{ChanH91,
title={Independence-Reducible Database Schemes},
author={Edward P. F. Chan and H{\'e}ctor J. Hern{\'a}ndez},
area={Database Theory},
pages={854--886},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Algorithms, Design, Theory},
keywords={Chase, constant-time maintanable schemes, functional
dependencies, independent database scheme, query evaluation,
representative instance},
cr-categories={H.2.1 [normal forms]; H.2.4 [query processing]}
}

@Article{BloomE91,
title={Floyd-{Hoare} Logic in Iteration Theories},
author={Stephen L. Bloom and Zolt{\'a} {\'E}sik},
area={Logic},
pages={887--934},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Algorithms, Theory},
keywords={Correction assertions, Hoare logic},
cr-categories={F.3.1 [assertions]; F.4.1 [logic programming]}
}

@Article{HalpernS91,
title={A Propositional Modal Logic of Time Intervals},
author={Joseph Y. Halpern and Yoav Shoham},
area={Logic},
pages={935--962},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
other-refs={POPL::BarringerKP86, POPL::Pratt79},
general-terms={Theory},
keywords={Axiomatizability, modal logic, temporal logic, temporal
reasoning, time intervals},
cr-categories={F.2.2 [complexity of proof procedures]; F.4.m; I.2.4
[representation languages]}
}

@Article{TiomkinK91,
title={Nonmonotonic Default Modal Logics},
author={Michael Tiomkin and Michael Kaminski},
area={Logic},
pages={963--984},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Theory},
keywords={Deduction theorem for modal logic, modal logic},
cr-categories={F.4.1; I.2.3 [nonmonotonic reasoning and belief
revision]; I.2.4}
}

@Article{BalasMPT91,
title={A Parallel Shortest Augmenting Path Algorithm for the
Assignment Problem},
author={Egon Balas and Donald Miller and Joseph Pekny and Paolo Toth},
area={Operations Research},
pages={985--1004},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Algorithms, Experimentation, Performance},
keywords={Assignment, matching, shortest augmenting paths, traveling
salesman problem},
cr-categories={C.1.2 [parallel processors]; F.2.1 [computation on
matrices]; G.1.0 [parallel algorithms]; G.1.3 [sparse and very large
systems]; G.1.6 [linear programming]; G.2.1 [combinatorial
algorithms]; G.2.2 [graph algorithms \and network problems \and path
and circuit problems]; I.1.2 [analysis of algorithms]}
}

@Article{Glasserman91,
title={Structural Conditions for Perturbation Analysis of Queuing
Systems},
author={Paul Glasserman},
area={Performance Analysis},
pages={1005--1025},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Design, Performance, Theory},
keywords={Gradient estimation, networks of queues, perturbation
analysis, sensitivity analysis, simulation},
cr-categories={C.4 [modeling techniques]; D.4.8 [queuing theory \and
simulation]; I.6.8 [discrete event]}
}

@Article{BergerR91,
title={Simulating {$(\log^c n)$}-Wise Independence in {$NC$}},
author={Bonnie Berger and John Rompel},
area={Theory of Computation},
pages={1026--1046},
journal=jacm,
month=oct,
year=1991,
volume=38,
number=4,
general-terms={Algorithms, Theory},
keywords={Discrepancy, removing randomness},
cr-categories={F.1.2 [parallelism \and probalistic computation]; F.2.2
[computations on discrete structures]; G.2.1 [combinatorial
algorithms]; G.2.2 [graph algorithms]}
}

                             January 1992
                         Volume 39, Number 1

@Article{ChazelleE92,
title={An Optimal Algorithm for Intersecting Line Segments in the
Plane},
author={Bernard Chazelle and Herbert Edelsbrunner},
area={Computational Geometry},
pages={1--54},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

@Article{Upfal92,
title={An {$O(\log N)$} Deterministic Packet-Routing Scheme},
author={Eli Upfal},
area={Computer Systems},
pages={55--70},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

@Article{Demolombe92,
title={Syntactical Characterization of a Subset of Domain-Independent
Formulas},
author={Robert Demolombe},
area={Database Theory},
pages={71--94},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

@Article{GoguenB92,
title={Institutions: Abstract Model Theory for Specification and
Programming},
author={Joseph A. Goguen and Rod M. Burstall},
area={Programming Languages and Methodology},
pages={95--146},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1,
other-refs={POPL::FutatsugiGJM85}
}

@Article{AcetoH92,
title={Termination, Deadlock, and Divergence},
author={L. Aceto and M. Hennessy},
area={Programming Languages and Methodology},
pages={147--187},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

@Article{DowdyCKT92,
title={Single-Class Bounds of Multi-Class Queuing Networks},
author={Lawrence W. Dowdy and Brian M. Carlson and Alan T. Krantz and
Satish K. Tripathi},
area={System Modeling and Analysis},
pages={188--213},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

@Article{BellareM92,
title={How to Sign Given Any Trapdoor Permutation},
author={Mihir Bellare and Silvio Micali},
area={Theory of Computation},
pages={214--233},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

@Article{AllenderH92,
title={Lower Bounds for the Low Hierarchy},
author={Eric Allender and Lane A. Hemachandra},
area={Theory of Computation},
pages={234--251},
journal=jacm,
month=jan,
year=1992,
volume=39,
number=1
}

                              April 1992
                         Volume 39, Number 2

@Article{DillencourtST92a,
title={A General Approach to Connected-Component Labeling for
Arbitrary Image Representations},
author={Michael B. Dillencourt and Hannan Samet and Markku Tamminen},
area={Data Structures and Algorithms},
pages={253--280},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2
}

@Article{KatajainenR92,
title={An Analysis of the Longest Match and the Greedy Heuristics in
Text Encoding},
author={Jyrki Katajainen and Timo Raita},
area={Data Structures and Algorithms},
pages={281--294},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2
}

@Article{RameshR92,
title={Nonlinear Pattern Matching in Trees},
author={R. Ramesh and I. V. Ramakrishnan},
area={Data Structures and Algorithms},
pages={295--316},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2,
other-refs={POPL::Chase87, POPL::FutatsugiGJM85}
}

@Article{Sprugnoli92,
title={The Generation of Binary Trees as a Numerical Problem},
author={Renzo Sprugnoli},
area={Data Structures and Algorithms},
pages={317--327},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2
}

@Article{FaginHV92,
title={What Can Machines Know?  On the Properties of Knowledge in
Distributed Systems},
author={Ronald Fagin and Joseph Y. Halpern and Moshe Y. Vardi},
area={Logic},
pages={328--376},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2,
other-refs={POPL::Pratt79}
}

@Article{GallierNRS92,
title={Theorem Proving Using Equational Matings and Rigid
{$E$}-Unification},
author={Jean Gallier and Paliath Narendran and Stan Raatz and Wayne
Snyder},
area={Logic},
pages={377--429},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2
}

@Article{Myers92,
title={A Four {Russians} Algorithm for Regular Expression Pattern
Matching},
author={Gene Myers},
area={String Processing},
pages={430--448},
journal=jacm,
month=apr,
year=1992,
volume=39,
number=2,
other-refs={POPL::Kennedy75}
}

                              July 1992
                         Volume 39, Number 3

@Article{HalpernZ92,
title={A Little Knowledge Goes a Long Way: Knowledge-Based Derivations
and Correctness Proofs for a Family of Protocols},
author={Joseph Y. Halpern and Lenore D. Zuck},
area={Distributed Computing},
pages={449--478},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3,
other-refs={POPL::ClarkeES83},
}

@Article{HeathI92,
title={The Pagenumber of Genus {$g$} Graphs is {$O(g)$}},
author={Lenwood S. Heath and Sorin Istrail},
area={Graph Theory},
pages={479--501},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{BillionnetCS92,
title={An Efficient Algorithm for a Task Allocation Problem},
author={A. Billionnet and M. C. Costa and A. Sutter},
area={Operations Research},
pages={502--518},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{EppsteinGGI92a,
title={Sparse Dynamic Programming {I}: Linear Cost Functions},
author={David Eppstein and Zvi Galil and Faffaele Giancarlo and
Giuseppe F. Italiano},
area={String Processing},
pages={519--545},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{EppsteinGGI92b,
title={Sparse Dynamic Programming {II}: Convex and Concave Cost
Functions},
author={David Eppstein and Zvi Galil and Faffaele Giancarlo and
Giuseppe F. Italiano},
area={String Processing},
pages={546--567},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{GreenbergM92,
title={How Fair Is Fair Queuing?},
author={Albert G. Greenberg and Neal Madras},
area={System Modeling and Analysis},
pages={568--598},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{BeaudryMT92,
title={The Membership Problem in Aperiodic Transformation Monoids},
author={M. Beaudry and P. McKenzie and D. Th{\'e}rien},
area={Theory of Computation},
pages={599--616},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{Ben-AmramG92,
title={On Pointers versus Addresses},
author={Amir M. Ben-Amram and Zvi Galil},
area={Theory of Computation},
pages={617--648},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{GasarchS92,
title={Learning via Queries},
author={William I. Gasarch and Carl H. Smith},
area={Theory of Computation},
pages={649--674},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}

@Article{GermanS92,
title={Reasoning about Systems with Many Processes},
author={Steven M. German and A. Prasad Sistla},
area={Theory of Computation},
pages={675--735},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3,
other-refs={POPL::EmersonL85, POPL::LichensteinP, POPL::MannaP87}
}

@Article{RazW92,
title={Monotone Circuits for Matching Require Linear Depth},
author={Ran Raz and Avi Wigderson},
area={Theory of Computation},
pages={736--744},
journal=jacm,
month=jul,
year=1992,
volume=39,
number=3
}


                             October 1992
                         Volume 39, Number 4

@Article{BorodinLS92,
title={An Optimal On-line Algorithm for Metrical Task System},
author={Allan Borodin and Nathan Linial and Michael E. Saks},
area={Analysis of Algorithms},
pages={745--763},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{FiatNSS92,
title={Nonoblivious Hashing},
author={Amos Fiat and Moni Naor and Jeanette P. Schmidt and Alan
Siegel},
area={Analysis of Algorithms},
pages={764--782},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{MansourS92,
title={The Intractability of Bounded Protocols for On-Line Sequence
Transmission over Non-{FIFO} Channels},
author={Yishay Mansour and Baruch Schieber},
area={Communication Protocols},
pages={783--799},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{DworkS92a,
title={Finite State Verifiers {I}: The Power of Interaction},
author={Cynthia Dwork and Larry Stockmeyer},
area={Complexity Theory},
pages={800--828},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}


@Article{DworkS92b,
title={Finite State Verifiers {II}: Zero Knowledge},
author={Cynthia Dwork and Larry Stockmeyer},
area={Complexity Theory},
pages={829--858},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{LundFKN92,
title={Algebraic Methods for Interactive Proof Systems},
author={Carsten Lund and Lance Fortnow and Howard Karloff and Noam
Nisan},
area={Complexity Theory},
pages={859--868},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{Shamir92,
title={{IP} = {PSPACE}},
author={Adi Shamir},
area={Complexity Theory},
pages={869--877},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4,
preliminary={FOCS::Shamir1990:11}
}

@Article{Shen92,
title={{IP} = {PSPACE}: Simplified Proof},
author={A. Shen},
area={Complexity Theory},
pages={878--880},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{HerlihyLMW92,
title={On the Correctness of Orphan Management Algorithms},
author={Maurice Herlihy and Nancy Lynch and Michael Merritt and
William Weihl},
area={Distributed Computation},
pages={881--930},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{CollinsDMP92,
title={A {VLSI} Decomposition of the {deBruijn} Graph},
author={Oliver Collins and Sam Dolinar and Robert McEliece and
Fabrizio Pollara},
area={VLSI Computation and Design},
pages={931--948},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{Debray92,
title={Efficient Dataflow Analysis of Logic Programs},
author={Saumya K. Debray},
area={Programming Languages},
pages={949--984},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

@Article{DillencourtST92b,
title={Corrigenda: ``{A} General Approach to Connected Component
Labeling for Arbitrary Image Representations''},
author={M. B. Dillencourt and H. Samet and M. Tamminen},
pages={985--986},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4
}

                             January 1993
                         Volume 40, Number 1

@Article{GallierNPRS93,
title={An Algorithm for Finding Canonical Sets of Ground Rewrite
Rules in Polynomial Time},
author={Jean Gallier and Paliath Narendran and David Plaisted and
Stan Raatz and Wayne Snyder},
area={Deductive Systems and Equational Reasoning},
pages={1--16},
journal=jacm,
month=jan,
year=1993,
volume=40,
number=1
}

@Article{DolevDWY93,
title={Perfectly Secure Message Transmission},
author={Danny Dolev and Cynthia Dwork and Orli Waarts and Moti
Yung},
area={Distributed Communication},
pages={17--47},
journal=jacm,
month=jan,
year=1993,
volume=40,
number=1
}

@Article{Hobby93,
title={Generating Automatically Tuned Bitmaps from Outlines},
author={John D. Hobby},
area={Graphics},
pages={48--94},
journal=jacm,
month=jan,
year=1993,
volume=40,
number=1
}

@Article{PittW93,
title={The Minimum Consistent {DFA} Problem Cannot be Approximated
within any Polynomial},
author={Leonard Pitt and Manfred K. Warmuth},
area={Learning Theory},
pages={95--142},
journal=jacm,
month=jan,
year=1993,
volume=40,
number=1
}

@Article{HarperHP93,
title={A Framework for Defining Logics},
author={Robert Harper and Furio Honsell and Gordon Plotkin},
area={Logic in Computer Science},
pages={143--184},
journal=jacm,
month=jan,
year=1993,
volume=40,
number=1
}

@Article{AngluinHK93,
title={Learning Read-Once Formulas with Queries},
author={Dana Angluin and Lisa Hellerstein and Marek Karpinski},
area={Machine Learning},
pages={185--210},
journal=jacm,
month=jan,
year=1993,
volume=40,
number=1
}

                              April 1993
                           Volume 40, No. 2

@Article{Bshouty93,
title={On the Complexity of Functions for Random Access Machines},
author={Nader H. Bshouty},
area={Analysis of Algorithms},
pages={211--223},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{LaPaugh93,
title={Recontamination Does Not Help to Search a Graph},
author={Andrea S. LaPaugh},
area={Analysis of Algorithms},
pages={224--245},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{McAllesterG93,
title={Taxonomic Syntax for First Order Inference},
author={David McAllester and Robert Givan},
area={Artificial Intelligence},
comment={Area erroneously listed as ``Computational Logic'' on
journal},
pages={246--283},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{McAllester93,
title={Automatic Recognition of Tractability in Inference Relations},
author={David A. McAllester},
area={Computational Logic},
pages={284--303},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{Nicol93,
title={The Cost of Conservative Synchronization in Parallel Discrete
Event Simulations},
author={David M. Nicol},
area={Computer System Modeling and Analysis},
pages={304--333},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{NeigerT93,
title={Simulating Synchronized Clocks and Common Knowledge in
Distributed Systems},
author={Gil Neiger and Sam Toueg},
area={Distributed Computing},
pages={334--367},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{LengauerW93,
title={Efficient Decision Procedures for Graph Properties on
Context-Free Graph Languages},
author={Thomas Lengauer and Egon Wanke},
area={Graph Theory},
pages={368--393},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

@Article{Leung93,
title={An Execution/Sleep Scheduling Policy for Serving an Additional
Job in Priority Queueing Systems},
author={Kin K. Leung},
area={Queueing Systems},
pages={394--417},
journal=jacm,
month=apr,
year=1993,
volume=40,
number=2
}

                              July 1993
                         Volume 40, Number 3

@Article{CoppersmithDRS93,
title={Random Walks on Weighted Graphs and Applications To On-line
Algorithms},
author={Don Coppersmith and Peter Doyle and Prabhakar Raghavan and
Marc Snir},
area={Analysis of Algorithms},
pages={421--453},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{KarloffR93,
title={Randomized Algorithms and Pseudorandom Numbers},
author={Howard J. Karloff and Prabhakar Raghavan},
area={Analysis of Algorithms},
pages={454--476},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{Baader93,
title={Unification in Commutative Theories, {Hilbert's} Basis Theorem
and {Gr\"obner} Bases},
author={Franz Baader},
area={Artificial Intelligence},
pages={477--503},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{MurrayR93,
title={Dissolution: Making Paths Vanish},
author={Neil V. Murray and Erik Rosenthal},
area={Logic in Computer Science--should be AI},
pages={504--535},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3,
general-terms={Algorithms, Theory},
keywords={Automated deduction, inference, matrix methods, path,
Prawitz analysis},
cr-categories={F.4.1[computational logic \and mechanical theorem
proving]; G.2.2; I.2.3[deduction \and metatheory; resolution]}
}

@Article{Johnson93,
title={Factorization and Circuit in the Connection Method},
author={C. A. Johnson},
area={Artificial Intelligence},
pages={536--557},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{Wang93,
title={Z-Module Reasoning: An Equality-Oriented Proving Method with
Built-in Ring Axioms},
author={{Tie-Cheng} Wang},
area={Artificial Intelligence},
pages={558--606},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{LinialMN93,
title={Constant Depth Circuits, {Fourier} Transform and Learnability},
author={Nathan Linial and Yishay Mansour and Noam Nisan},
area={Complexity Theory},
pages={607--620},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{MehlhornT93,
title={Dynamic Interpolation Search},
author={Kurt Mehlhorn and Athanasios Tsakalidis},
area={Data Structures and Algorithms},
pages={621--634},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{KreveldO93,
title={Union-Copy Structures and Dynamic Segment Trees},
author={Marc J. van Kreveld and Mark H. Overmars},
area={Data Structures},
pages={635--652},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{BaetenBK93,
title={Decidability of Bisimulation Equivalence for Processes
Generating Context-Free Languages},
author={J. C. M. Baeten and J. A. Bergstra and J. W. Klop},
area={Formal Languages},
pages={653--682},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{GaifmanMSV93,
title={Undecidable Optimization Problems for Database Logic Programs},
author={Haim Gaifman and Harry Mairson and Yehoshua Sagiv and Moshe
Y. Vardi},
area={Logic in Computer Science},
pages={683--713},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{NelsonT93,
title={A Performance Evaluation of Several Priority Policies for
Parallel Processing Systems},
author={Randolph Nelson and Donald Towsley},
area={Operations Research},
pages={714--740},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{BhattC93,
title={Taking Random Walks to Grow Trees in Hypercubes},
author={Sandeep Bhatt and {Jin-Yi} Cai},
area={Parallel Computation},
pages={741--764},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

@Article{KarpZ93,
title={Randomized Parallel Algorithms for Backtrack Search and
Branch-and-Bound Computation},
author={Richard M. Karp and Yanjun Zhang},
area={Parallel Computation},
pages={765--789},
journal=jacm,
month=jul,
year=1993,
volume=40,
number=3
}

                            September 1993
                         Volume 40, Number 4

@Article{CohenM93,
title={Strongly Polynomial-Time and {NC} Algorithms for Detecting
Cycles in Periodic Graphs},
author={Edith Cohen and Nimrod Megiddo},
area={Combinatorial Optimization},
pages={791--830},
journal=jacm,
month=sep,
year=1993,
volume=40,
number=4
}

@Article{YuDL93,
title={On the Analytical Modeling of Database Concurrency Control},
author={Philip S. Yu and Daniel M. Dias and Stephen S. Lavenberg},
area={Computer System Modelling and Analysis},
pages={831--872},
journal=jacm,
month=sep,
year=1993,
volume=40,
number=4
}

@Article{AfekADGMS93,
title={Atomic Snapshots of Shared Memory},
author={Yehuda Afek and Hagit Attiya and Danny Dolev and Eli Gafni
and Michael Merritt and Nir Shavit},
area={Distributed Computing},
pages={873--890},
journal=jacm,
month=sep,
year=1993,
volume=40,
number=4
}

@Article{AfratiP93,
title={The Parallel Complexity of Simple Logic Programs},
author={Foto Afrati and Christos H. Papadimitriou},
area={Languages and Automata Theory},
pages={891--916},
journal=jacm,
month=sep,
year=1993,
volume=40,
number=4
}

@Article{HalpernT93,
title={Knowledge, Probability, and Adversaries},
author={Joseph Y. Halpern and Mark R. Tuttle},
area={Logic in Computer Science},
pages={917--962},
journal=jacm,
month=sep,
year=1993,
volume=40,
number=4
}

@Article{MarekST93,
title={Modal Nonmonotonic Logics: Ranges, Characterization,
Computation},
author={V. Wiktor Marek and Grigori F. Schwarz and Miros{\l}aw
Truszczy{\'n}ski},
area={Logic in Computer Science--should be AI},
pages={963--990},
journal=jacm,
month=sep,
year=1993,
volume=40,
number=4
}

                            November 1993
                         Volume 40, Number 5

@Article{CoffmanG93,
title={Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive
Two-Processor Scheduling},
author={E. G. {Coffman, Jr.} and M. R. Garey},
area={Complexity of Algorithms},
pages={991--1018},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{LuoT93,
title={On the Communication Complexity of Distributed Algebraic
Computation},
author={{Zhi-Quan} Luo and John N. Tsitsiklis},
area={Complexity of Algorithms},
pages={1019--1047},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{DonaldXCR93,
title={Kinodynamic Motion Planning},
author={Bruce Donald and Patrick Xavier and John Canny and John
Reif},
area={Computational Geometry},
pages={1048--1066},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{Tay93,
title={On the Optimality of Strategies for Multiple Joins},
author={Y. C. Tay},
area={Database Theory},
pages={1067--1086},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{FeketeLMS93,
title={The Impossibility of Implementing Reliable Communication in
the Face of Crashes},
author={Alan Fekete and Nancy Lynch and Yishay Mansour and John
Spinelli},
area={Distributed Computing},
pages={1087--1107},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{GolumbicS93,
title={Complexity and Algorithms for Reasoning about Time: A
Graph-Theoretic Approach},
author={Martin Charles Golumbic and Ron Shamir},
area={Graph Theory},
pages={1108--1133},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{ArnborgCPS93,
title={An Algebraic Theory of Graph Reduction},
author={Stefan Arnborg and Bruno Courcelle and Andrzej Proskurowski
and Detlef Seese},
area={Logic in Computer Science},
pages={1134--1164},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{FonluptN93,
title={Dynamic Programming and the Graphical Traveling Salesman
Problem},
author={Jean Fonlupt and Armand Nachef},
area={Operations Research},
pages={1165--1187},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{Jean-MarieG93,
title={Parallel Queues with Resequencing},
author={Alain Jean-Marie and Levent G{\"u}n},
area={Computer Systems Modeling and Analysis},
pages={1188--1208},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{BaccelliLT93,
title={Extremal Scheduling of Parallel Processing with and without
Real-Time Constraints},
author={Fran{\c{c}}ois Baccelli and Zhen Liu and Don Towsley},
area={Computer Systems Modeling and Analysis},
pages={1209--1237},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

@Article{Knessl93,
title={On the Sojourn Time Distribution in a Finite Capacity
Processor Shared Queue},
author={Charles Knessl},
area={Computer Systems Modeling and Analysis},
pages={1238--1301},
journal=jacm,
month=nov,
year=1993,
volume=40,
number=5
}

Author Index -- pages 1302--1304

Subject Index -- pages 1305--306

                             January 1994
                         Volume 41, Number 1

@Article{FischerP94,
title={Fishspear: A Priority Queue Algorithm},
author={Michael J. Fischer and Michael S. Paterson},
area={Analysis of Algorithms},
pages={3--30},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}

@Article{Rockmore94,
title={Efficient Computation of {Fourier} Inversion for Finite
Groups},
author={Daniel N. Rockmore},
area={Complexity of Algorithms},
pages={31--66},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}

@Article{KearnsV94,
title={Cryptographic Limitations on Learning {Boolean} Formulae and
Finite Automata},
author={Michael Kearns and Leslie Valiant},
area={Complexity Theory},
pages={67--95},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}

@Article{OrponenKSW94,
title={Instance Complexity},
author={Pekka Orponen and {Ker-I} Ko and Uwe Sch{\"o}ning and Osamu
Watanabe},
area={Complexity Theory},
pages={96--121},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}

@Article{AttiyaDLS94,
title={Bounds on the Time to Reach Agreement in the Presence of
Timing Uncertainty},
author={Hagit Attiya and Cynthia Dwork and Nancy Lynch and Larry
Stockmeyer},
area={Distributed Computing},
pages={122--152},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}

@Article{Baker94,
title={Approximation Algorithms for {NP}-Complete Problems on Planar
Graphs},
author={Brenda S. Baker},
area={Graph Theory},
pages={153--180},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}

@Article{AlurH94,
title={A Really Temporal Logic},
author={Rajeev Alur and Thomas A. Henzinger},
area={Logic in Computer Science},
pages={181--204},
journal=jacm,
month=jan,
year=1994,
volume=41,
number=1
}


                              March 1994
                         Volume 41, Number 2

@Article{DubinerMG94,
title={Faster Tree Pattern Matching},
author={Moshe Dubiner and Zvi Galil and Edith Magen},
area={Complexity of Algorithms},
pages={205--213},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{KhullerV94,
title={Biconnectivity Approximations and Graph Carvings},
author={Samir Khuller and Uzi Vishkin},
area={Complexity of Algorithms},
pages={214--235},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{BachmairD94,
title={Equational Inference, Canonical Proofs, and Proof Orderings},
author={Leo Bachmair and Nachum Dershowitz},
area={Deductive Systems and Equational Reasoning},
pages={236--276},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{AbrahamsonAHK94,
title={Tight Lower Bounds for Probabilistic Solitude Verification on
Anonymous Rings},
author={Karl Abrahamson and Andrew Adler and Lisa Higham and David
Kirkpatrick},
area={Distributed Computing},
pages={277--310},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{SinghAG94,
title={The Elusive Atomic Register},
author={Ambuj K. Singh and James H. Anderson and Mohamed G. Gouda},
area={Distributed Computing},
pages={311--339},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{FaginH94,
title={Reasoning about Knowledge and Probability},
author={Ronald Fagin and Joseph Y. Halpern},
area={Logic in Computer Science},
pages={340--367},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{KfouryTU94,
title={An Analysis of {ML} Typability},
author={A. J. Kfoury and J. Tiuryn and P. Urzyczyn},
area={Logic in Computer Science},
pages={368--398},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{CosnardD94,
title={Optimal Algorithms for Parallel Givens Factorization on a
Coarse-Grained {PRAM}},
author={Michael Cosnard and El Mostafa Daoudi},
area={Numerical Computation},
pages={399--421},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

@Article{AlonM94,
title={Parallel Linear Programming in Fixed Dimension Almost Surely
in Constant Time},
author={Noga Alon and Nimrod Megiddo},
area={Operations Research},
pages={422--434},
journal=jacm,
month=mar,
year=1994,
volume=41,
number=2
}

                               May 1994
                         Volume 41, Number 3

@Article{LadkinM94,
title={On Binary Constraint Problems},
author={Peter B. Ladkin and Roger D. Maddux},
area={Artificial Intelligence},
pages={435--469},
journal=jacm,
month=may,
year=1994,
volume=41,
number=3
}

@Article{Blum94,
title={New Approximation Algorithms for Graph Coloring},
author={Avrim Blum},
area={Complexity of Algorithms},
pages={470--516},
journal=jacm,
month=may,
year=1994,
volume=41,
number=3
}

@Article{DrusinskyH94,
title={On the Power of Bounded Concurrency {I}: Finite Automata},
author={Doron Drusinsky and David Harel},
area={Logic in Computer Science},
pages={517--539},
journal=jacm,
month=may,
year=1994,
volume=41,
number=3
}

@Article{HirstH94,
title={On the Power of Bounded Concurrency {II}: Pushdown Automata},
author={Tirza Hirst and David Harel},
area={Logic in Computer Science},
pages={540--554},
journal=jacm,
month=may,
year=1994,
volume=41,
number=3
}

@Article{RivestS94,
title={Diversity-Based Inference of Finite Automata},
author={Ronald L. Rivest and Robert E. Schapire},
area={Machine Learning},
pages={555--589},
journal=jacm,
month=may,
year=1994,
volume=41,
number=3
}

                              July 1994
                         Volume 41, Number 4

@Article{BuntineB94,
title={On Solving Equations and Disequations},
author={Wray L. Buntine and Hans-J{\"u}rgen B{\"u}rckert},
area={Artificial Intelligence},
pages={591--629},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4,
other-refs={POPL::JaffarL87, POPL::JouannaudK84}
}

@Article{BlumJLTY94,
title={Linear Approximation of Shortest Superstrings},
author={Avrim Blum and Tao Jiang and Ming Li and John Tromp and
Mihalis Yannakakis},
area={Complexity of Algorithms},
pages={630--647},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}

@Article{ConwayPT94,
title={Efficient Decomposition Methods for the Analysis of
Multi-Facility Blocking Models},
author={Adrian E. Conway and Eugene Pinsky and Srinivasan
Tridandapani},
area={Computer System Modeling and Analysis},
pages={648--675},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}

@Article{LuiM94,
title={Computing Bounds on Steady State Availability of Repairable
Computer Systems},
author={John C. S. Lui and Richard R. Muntz},
area={Computer System Modeling and Analysis},
pages={676--707},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}

@Article{BellW94,
title={The Relationship between Greedy Parsing and Symbolwise Text
Compression},
author={Timothy C. Bell and Ian H. Witten},
area={Data Structures and Analysis of Algorithms},
pages={708--724},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}

@Article{AttiyaLS94,
title={Are Wait-Free Algorithms Fast?},
author={Hagit Attiya and Nancy Lynch and Nir Shavit},
area={Distributed Computing},
pages={725--763},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}

@Article{ReifS94a,
title={Motion Planning in the Presence of Moving Obstacles},
author={John Reif and Micha Sharir},
area={Graph Theory and Combinatorial Structures},
pages={764--790},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}

@Article{GaoK94,
title={Channel Routing of Multiterminal Nets},
author={Shaodi Gao and Michael Kaufmann},
area={VLSI Computation and Design},
pages={791--818},
journal=jacm,
month=jul,
year=1994,
volume=41,
number=4
}


                            September 1994
                         Volume 41, Number 5

@Article{RathmannWM94,
title={Circumscription with Homomorphisms: Solving the Equality and
Counterexample Problems},
author={Peter K. Rathmann and Marianne Winslett and Mark Manasse},
area={Artificial Intelligence},
pages={819--873},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5
}

@Article{GlassN94,
title={The Turn Model for Adaptive Routing},
author={Christopher J. Glass and Lionel M. Ni},
area={Computer Architecture},
pages={874--902},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5
}

@Article{DalleryLT94,
title={Equivalence, Reversibility, Symmetry and Concavity Properties
in Fork-Join Queuing Networks with Blocking},
author={Yves Dallery and Zhen Liu and Don Towsley},
area={Computer System Modelling and Analysis},
pages={903--942},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5
}

@Article{DriscollST94,
title={Fully Persistent Lists with Catenation},
author={James R. Driscoll and Daniel D. K. Sleator and Robert E.
Tarjan},
area={Complexity of Algorithms},
pages={943--959},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5,
other-refs={POPL::Myers84}
}

@Article{LundY94,
title={On the Hardness of Approximating Minimization Problems},
author={Carsten Lund and Mihalis Yannakakis},
area={Complexity Theory},
pages={960--981},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5,
preliminary={STOC::LundY1993}
}

@Article{StorerR94,
title={Shortest Paths in the Plane with Polygonal Obstacles},
author={James A. Storer and John H. Reif},
area={Data Structures and Analysis of Algorithms},
pages={982--1012},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5
}

@Article{ReifS94b,
title={A Single-Exponential Upper Bounds for Finding Shortest Paths in
Three Dimensions},
author={John H. Reif and James A. Storer},
area={Data Structures and Analysis of Algorithms},
pages={1013--1019},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5
}

@Article{AspnesHS94,
title={Counting Networks},
author={James Aspnes and Maurice Herlihy and Nir Shavit},
area={Distributed Computing},
pages={1020--1048},
journal=jacm,
month=sep,
year=1994,
volume=41,
number=5
}


                            November 1994
                         Volume 41, Number 6

@Article{AtallahGK94,
title={Parallel Algorithms for Evaluating Sequences of
Set-Manipulation Operations},
author={Mikhail J. Atallah and Michael T. Goodrich and S. Rao
Kosaraju},
area={Complexity of Algorithms},
pages={1049--1088},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{Rabin94,
title={Robust Sharing of Secrets when the Dealer Is Honest or
Cheating},
author={Tal Rabin},
area={Complexity of Algorithms},
pages={1089--1109},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{RossTW94,
title={Monte {Carlo} Summation and Integration Applied to Multiclass
Queuing Networks},
author={Keith W. Ross and Danny H. K. Tsang and Jie Wang},
area={Computer System Modeling and Analysis},
pages={1110--1135},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{Karp94,
title={Probabilistic Recurrence Relations},
author={Richard M. Karp},
area={Data Structures and Analysis of Algorithms},
pages={1136--1150},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{NaughtonR94,
title={How to Forget the Past without Repeating It},
author={Jeffrey F. Naughton and Raghu Ramakrishnan},
area={Database Theory},
pages={1151--1177},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{BellNNS94,
title={Mixed Integer Programming Methods for Computing Nonmonotonic
Deductive Databases},
author={Colin Bell and Anil Nerode and Raymond T. Ng and V. S.
Subrahmanian},
area={Deductive Systems and Equational Reasoning},
pages={1178--1215},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6,
other-refs={POPL::JaffarL87}
}

@Article{Ross94,
title={Modular Stratification and Magic Sets for Datalog Programs with
Negation},
author={Kenneth A. Ross},
area={Deductive Systems and Equational Reasoning},
pages={1216--1266},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{AfekAFFLMWZ94,
title={Reliable Communication Over Unreliable Channels},
author={Yehuda Afek and Hagit Attiya and Alan Fekete and Michael
Fischer and Nancy Lynch and Yishay Mansour and Dai-Wei Wang and Lenore
Zuck},
area={Distributed Computing},
pages={1267--1297},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{KearnsLV94,
title={Learning {Boolean} Formulas},
author={Michael Kearns and Ming Li and Leslie Valiant},
area={Formal Languages and Complexity Theory},
pages={1298--1328},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

@Article{Motwani94,
title={Average-Case Analysis of Algorithms for Matchings and Related
Problems},
author={Rajeev Motwani},
area={Operations Research},
pages={1329--1356},
journal=jacm,
month=nov,
year=1994,
volume=41,
number=6
}

                             January 1995
                         Volume 42, Number 1

@Article{EiterG95,
title={The Complexity of Logic-Based Abduction},
author={Thomas Eiter and Georg Gottlob},
area={Artificial Intelligence},
pages={3--42},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Theory},
keywords={Abduction, Complexity Analysis, Diagnosis, Reasoning,
Propositional Logic},
cr-categories={I.2.3, I.2.4, F.2.2, F.4.1},
preliminary={STACS::EitherG1993}
}

@Article{NebelB95,
title={Reasoning About Temporal Relations: A Maximal Tractable
Subclass of {Allen's} Interval Algebra},
author={Bernhard Nebel and Hans-J{\"u}rgen B{\"u}rckert},
area={Artificial Intelligence},
pages={43--66},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Algorithms, Theory},
keywords={Constraint satisfaction, interval algebra, qualitative
reasoning, temporal reasoning},
cr-categories={F.2.2[sequencing and scheduling]; I.2.4[relation
systems]}
}

@Article{CallahanK95,
title={A Decomposition of Multidimensional Point Sets with
Applications to {$k$}-Nearest-Neighbors and {$n$}-Body Potential
Fields},
author={Paul B. Callahan and S. Rao Kosaraju},
area={Computational Geometry},
pages={67--90},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Algorithms, Theory},
keywords={All nearest neighbors, fast multipole method},
cr-categories={F.2.2[geometrical problems and computation];
F.1.2[parallelism and concurrency]}
}

@Article{ChienK95,
title={Planar-Adaptive Routing: Low-Cost Adaptive Networks for
Multiprocessors},
author={Andrew A. Chien and Jae H. Kim},
area={Computer Architecture},
pages={91--123},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Algorithms, Performance, Reliability},
keywords={Adaptive routing, fault tolerance, interconnection networks,
multicomputers, packet routing, parallel processing,
transmission-order preservation},
cr-categories={B.4.3; C.2.1}
}

@Article{AttiyaBD95,
title={Sharing Memory Robustly in Message-Passing Systems},
author={Hagit Attiya and Amotz Bar-Noy and Danny Dolev},
area={Distributed Computing},
pages={124--142},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Algorithms, Theory, Reliability},
keywords={Atomic registers, emulation, fault-tolerance, message
passing, processor and link failures, shared memory, and
wait-freedom},
cr-categories={C.1.2[multiple-instruction-stream, multiple-data-stream
processors (MIMD)]; C.2.1[distributed networks]; C.2.4;
D.4.1[concurrency, multiprocessing/multiprogramming, synchronization];
F.1.1[relations among models]}
}

@Article{DolevHSS95,
title={Dynamic Fault-Tolerant Clock Synchronization},
author={Danny Dolev and Joseph Y. Halpern and Barbara Simons and Ray
Strong},
area={Distributed Computing},
pages={143--185},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={General Terms: Algorithms, performance, reliability,
theory},
keywords={Byzantine failures, clock synchronization, fault-tolerance,
time-of-day clock},
cr-categories={C.2.4[distributed applications, distributed databases,
network operating systems]; C.4[reliability, availability, and
serviceability]; D.4.1[synchronization]; D.4.5[fault-tolerance]}
}

@Article{HaldarV95,
title={Constructing 1-Writer Multireader Multivalued Atomic Variable
from Regular Variables},
author={S. Haldar and K. Vidyasankar},
area={Distributed Computing},
pages={186--203},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Algorithms, Theory, Verification},
keywords={Nonatomic operation execution, reader and writer, shared
variable-safe, regular and atomic, wait-freedom},
cr-categories={B.3.2[shared memory]; B.4.3[asynchronous/synchronous
operation]; D.1.3; D.4.1[concurrency,
multiprocessing/multiprogramming]; D.4.4[buffering]}
}

@Article{ChangN95,
title={Bounds on the Speedup and Efficiency of Partial
Synchronization in Parallel Processing Systems},
author={C. S. Chang and R. Nelson},
area={Parallel Computation},
pages={204--231},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Measurement, Performance},
keywords={Large deviations theory, synchronization},
cr-categories={C.1.2[parallel processors]; C.4[performance
attributes]; G.M[queuing theory]}
}

@Article{BloomIM95,
title={Bisimulation Can't Be Traced},
author={Bard Bloom and Sorin Istrail and Albert R. Meyer},
area={Programming Languages and Methodology},
pages={232--268},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Languages, Theory, Verification},
keywords={Bisimulation, structural operational semantics, process
algebra, CCS},
cr-categories={D.3.1[semantics]; D.3.3[concurrent programming
structures]; F.3.2[algebraic approaches to semantics; operational
semantics]; I.6.2}
}

@Article{BlumK95,
title={Designing Programs that Check Their Work},
author={Manuel Blum and Sampath Kannan},
area={Programming Languages and Methodology},
pages={269--291},
journal=jacm,
month=jan,
year=1995,
volume=42,
number=1,
general-terms={Algorithms, Design, Reliability, Theory, Verification},
keywords={Interactive proofs, probabilistic algorithms, program
checking, program verification, testing},
cr-categories={D.2.4[correctness proofs; reliability]; F.2.0; F.3.1;
G.3[probabilistic algorithms (including Monte Carlo)]}
}

                              March 1995
                         Volume 42, Number 2

@Article{LinS95,
title={Provably Correct Theories of Action},
author={Fangzhen Lin and Yoav Shoham},
area={Artificial Intelligence},
pages={293--320},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Human Factors, Theory},
keywords={Concurrent actions, the frame problem, reasoning about
actions, temporal reasoning},
cr-categories={I.2.3[circumscription]; I.2.4[the situation calculus]}
}

@Article{KargerKT95,
title={A Randomized Linear-Time Algorithm to Find Minimum Spanning
Trees},
author={David R. Karger and Philip N. Klein and Robert E. Tarjan},
area={Complexity of Algorithms},
pages={321--328},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Algorithms},
keywords={Matroid, minimum spanning tree, network, randomized
algorithm},
cr-categories={F.2.2[computations on discrete structures]; G.2.2[graph
algorithms, network problems, trees]; G.3[probabilistic algorithms
(including Monte Carlo)], I.5.3}
}

@Article{WangZC95,
title={Decomposition of Magic Rewriting},
author={Ke Wang and Weining Zhang and Siu-Cheung Chau},
pages={329--381},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Algorithms, Theory},
keywords={Arity reduction, bottom-up evaluation, database, deductive
database, logic program, magic rewriting, program decomposition},
cr-categories={F.4.1[logic programming]; H.2.4[query processing];
I.2.3[deduction and logic programming]}
}

@Article{TsitsiklisS95,
title={On the Average Communication Complexity of Asynchronous
Distributed Algorithms},
author={John N. Tsitsiklis and George D. Stamoulis},
area={Distributed Computing},
pages={382--400},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Algorithms, performance},
keywords={asynchronous distributed algorithms},
cr-categories={C.2.1[network communication]; G.1.0[parallel
algorithms]; G.m[Queueing theory]]}
}

@Article{KurtzMR95,
title={The Isomorphism Conjecture Fails Relative to a Random Oracle},
author={Stuart A. Kurtz and Stephen R. Mahaney and James S. Royer},
area={Formal Languages and Complexity Theory},
pages={401--420},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Theory},
keywords={Isomorphism, conjecture, randomness},
cr-categories={F.m}
}

@Article{Gottlob95a,
title={{NP} Trees and {Carnap's} Modal Logic},
author={Georg Gottlob},
area={Logic in Computer Science},
pages={421--457},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Theory},
keywords={Autoepistemic logic, bounded query computation, epistemic
logic, modal logic, NP, oracle, trees},
cr-categories={F.1.2[relations among complexity classes];
F.2.2[Complexity of proof procedures; computations on discrete
structures]; F.4.1[Computational logic]; I.2.3[Nonmonotonic reasoning
and belief revision]; I.2.4},
preliminary={FOCS::Gottlob1993}
}

@Article{NicolaV95,
title={Three Logics for Branching Bisimulation},
author={Rocco De Nicola and Frits Vaandrager},
area={Logic in Computer Science},
pages={458--487},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Theory, verification},
keywords={Backward modalities, branching bisimulation equivalence,
concurrency, CTL*, doubly labeled transition systems, Hennessy-Milner
logic, Kripke structures, labeled transition systems, reactive
systems, semantics, stuttering equivalence, until operations},
cr-categories={F.1.1, F.3.1},
preliminary={LICS::NicolaV1990}
}

@Article{Clarkson95,
title={Las {Vegas} Algorithms for Linear and Integer Programming When
the Dimension is Small},
author={Kenneth L. Clarkson},
pages={488--499},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Algorithms, Theory},
cr-categories={G.1.6[integer programming, nonlinear programming];
G.3}
}

@Article{BergerBBL95,
title={Nearly Optimal Algorithms and Bounds for Multilayer Channel
Routing},
author={Bonnie Berger and Martin Brady and Donna Brown and Tom
Leighton},
area={Parallel Computation},
pages={500--542},
journal=jacm,
month=mar,
year=1995,
volume=42,
number=2,
general-terms={Design, Theory},
keywords={Channel routing, multilayer routing, VLSI layout},
cr-categories={B.7.2[placement and routing]; F.2.2[routing and
layout]}
}

                               May 1995
                         Volume 42, Number 3

@Article{BeekD95,
title={On the Minimality and Global Consistency of Row-Convex
Constraint Networks},
author={Peter van Beek and Rina Dechter},
pages={543--561},
area={Artificial Intelligence},
journal=jacm,
month=may,
year=1995,
volume=42,
number=3,
general-terms={Algorithms, Theory},
keywords={Consecutive ones property, constraint-based reasoning,
constraint networks, constraint satisfaction problems, path
consistency, relations, row convexity},
cr-categories={F.2.2 [computations on discrete structures]; G.2.2
[permutations and combinations]; I.2.4 [relation systems]}
}

@Article{ComptonR95,
title={Expected Deadlock Time in a Multiprocessing System},
author={Kevin J. Compton and Chinya Ravishankar},
pages={562--583},
area={Graph Theory and Combinatorial Structures},
journal=jacm,
month=may,
year=1995,
volume=42,
number=3,
general-terms={Theory},
keywords={Asymptotic analysis, expected time analysis, singularity
analysis},
cr-categories={D.4.1 [deadlocks]; [multiprocessing/multiprogramming];
F.2.2 [computations on discrete structures]; G.2.1 [generating
functions]; G.2.2 [path and circuit problems]}
}

@Article{KorilisL95,
title={On the Existence of Equilibria in Noncooperative Optimal Flow
Control},
author={Yannis A. Korilis and Aurel A. Lazar},
pages={584--613},
area={Operations Research},
journal=jacm,
month=may,
year=1995,
volume=42,
number=3,
general-terms={Performance, Theory},
keywords={Fixed points, flow control, game theory, Nash equilibria},
cr-categories={C.2.3 [network management]; D.4.8 [qeueing theory];
G.1.6 [constrained optimization, linear programming]}
}

@Article{BayB95,
title={Deterministic On-Line Routing on Area-Universal Networks},
author={Paul Bay and Gianfranco Bilardi},
pages={614--640},
area={Parallel Computation},
journal=jacm,
month=may,
year=1995,
volume=42,
number=3,
general-terms={Algorithms, Theory},
keywords={Area-universal, fat-tree, general purpose},
cr-categories={C.1.2 [interconnection architectures]; C.2.1 [network
communications, network topology]; F.1.2 [parallelism and
concurrency]; F.2.2 [computation on discrete structures]; [routing and
layout]; F.2.3},
preliminary={FOCS::BayB1990}
}

@Article{BirmanGHRS95,
title={An Optimal Service Policy for Buffer Systems},
author={Alexander Birman and H. Richard Gail and Sidney L. Hantler
and Zvi Rosberg and Moshe Sidi},
pages={641--657},
area={Parallel Computation},
journal=jacm,
month=may,
year=1995,
volume=42,
number=3,
general-terms={Algorithms, Design, Performance},
keywords={Buffer overflow, gradual input, multiplexor, parallel
queues, service discipline, switch},
cr-categories={C.2.1 [packet networks]; C.4 [performance attributes];
D.4.4 [buffering]; D.4.8 [queueing theory]}
}

@Article{OHearnT95,
title={Parametricity and Local Variables},
author={P. W. O'Hearn and R. D. Tennent},
pages={658--709},
area={Programming Languages and Methodology},
journal=jacm,
month=may,
year=1995,
volume=42,
number=3,
other-refs={POPL::AbramskyJ91, POPL::MeyerS88, POPL::Mitchell86,
CACM::Backus63, POPL::OHearnT93, POPL::Reynolds78},
general-terms={Languages, Theory},
keywords={Algol-like languages, local state, logical relations,
parametric polymorphism},
cr-categories={D.3.1 [semantics]; F.3.2 [denotational semantics]}
}

                              July 1995
                         Volume 42, Number 4

@Article{Gottlob95b,
title={Translating Default Logic into Standard Autoepistemic Logic},
author={Georg Gottlob},
pages={711--740},
area={Artificial Intelligence},
journal=jacm,
month=jul,
year=1995,
volume=42,
number=4,
general-terms={Theory},
keywords={Autoepistemic logic, default logic, nonmonotonic modal
logic, reasoning, translation},
cr-categories={F.4.1 [Computational Logic]; I.2.0 [philosophical
foundation]; I.2.3 [Nonmonotonic reasoning and belief revision]; I.2.4
[representation languages]}
}

@Article{KiferLW95,
title={Logical Foundations of Object-Oriented and Frame-Based
Languages},
author={Michael Kifer and Georg Lausen and James Wu},
pages={741--843},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
month=jul,
year=1995,
volume=42,
number=4,
general-terms={Languages, Theory},
keywords={Object-oriented programming, frame-based languages,
deductive databases, logic programming, semantics, proof theory,
typing, nonmonotonic inheritance},
cr-categories={H.2.1 [query languages]; I.2.3 [deduction, logic
programming, nonmonotonic reasoning]; F.4.1 [logic programming,
mechanical theorem proving]}
}

@Article{AlonYZ95,
title={Color-coding},
author={Noga Alon and Raphael Yuster and Uri Zwick},
pages={844--856},
area={Graph Theory and Combinatorial Structures},
journal=jacm,
month=jul,
year=1995,
volume=42,
number=4,
cr-categories={G.2.2 [graph algorithms \and path and circuit
problems]},
preliminary={STOC::AlonYZ1994}
}

@Article{CourcoubetisY95,
title={The Complexity of Probabilistic Verification},
author={Costas Courcoubetis and Mihalis Yannakakis},
pages={857--907},
area={Logic in Computer Science},
journal=jacm,
month=jul,
year=1995,
volume=42,
number=4,
general-terms={Algorithms, Theory, Verification},
keywords={Automata, EXPTIME-complete, Markov chain, model checking,
probabilistic algorithm, PSPACE-complete, temporal logic},
cr-categories={D.2.4; F.2.2 [complexity of proof procedures]; F.3.1
[mechanical verification]; G.3 [probabilistic algorithms]}
}

@Article{Galil95,
title={A Constant-Time Optimal Parallel String-Matching Algorithm},
author={Zvi Galil},
pages={908--918},
area={Parallel Computation},
journal=jacm,
month=jul,
year=1995,
volume=42,
number=4,
general-terms={Algorithms, Theory},
keywords={Constant time, CRCW-PRAM, lion hunting, optimal parallel
algorithm, period, string matching},
cr-categories={F.2.2 [computations on discrete structures]}
}

@Article{NodineV95,
title={Greed Sort: Optimal Deterministic Sorting on Parallel Disks},
author={Mark H. Nodine and Jeffrey Scott Vitter},
pages={919--933},
area={Parallel Computation},
journal=jacm,
month=jul,
year=1995,
volume=42,
number=4,
general-terms={Algorithms},
keywords={I/O complexity, parallel disks, parallel I/O, merge sort},
cr-categories={B.4.4 [worst-case analysis]; F.1.2 [parallelism and
concurrency]; F.2.2 [sorting and searching]; E.5 [sorting/searching]}
}

                            September 1995
                         Volume 42, Number 5

@Article{ChoudhuryLW95,
title={Calculating Normalization Constants of Closed Queueing Networks
by Numerically Inverting Their Generating Functions},
author={Gagan L. Choudhury and Kin K. Leung and Ward Whitt},
pages={935--970},
area={Computer System Modeling and Analysis},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Algorithms, Performance, Theory},
keywords={closed queueing networks, dimension reduction, Euler
summation, generating function, normalization constant, numerical
transform inversion, partition function, performance analysis,
product-form model, scaling},
cr-categories={C.4 [modeling techniques]; F.2.1 [computation of
transformations]; G.1.4 [multiple quadrature]; G.1.m [miscellaneous]}
}

@Article{KoutsoupiasP95,
title={On the {$k$}-Server Conjecture},
author={Elias Koutsoupias and Christos H. Papadimitriou},
pages={971--983},
area={Data Structures and Analysis of Algorithms},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Algorithms, theory, performance},
keywords={Competitive analysis, $k$-server problem, on-line
algorithms, potential, quasiconvexity, work function},
cr-categories={F.2.2 [computation on discrete structures]; G.2.1
[combinatorial algorithms]},
preliminary={STOC::KoutsoupiasP1994:507}
}

@Article{Verma95,
title={A Theory of Using History for Equational Systems with
Applications},
author={Rakesh M. Verma},
pages={984--1020},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Algorithms, Theory},
keywords={Congruence-closure algorithm, equational logic, rewrite
systems, rewrite system transformation, proof theory, term rewriting},
cr-categories={F.4.1[computational logic \and mechanical theorem
proving \and proof theory]; I.2.3[deduction]},
preliminary={FOCS::Verma1991}
}

@Article{AwerbuchP95,
title={Online Tracking of Mobile Users},
author={Baruch Awerbuch and David Peleg},
pages={1021--1058},
area={Distributed Computing},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Design, Protocols, Reliability, Theory, Verification},
keywords={Bounded packet header, bounded protocol, ideal transmission
cost, lookahead, non-FIFO channels, receiver-driven protocol,
recoverable protocol, recovery cost, sequence transmission problem},
cr-categories={B.4.4 [formal models, verification, worst-case
analysis]; C.2.2 [protocol architecture, protocol verification]; D.4.4
[network communications]; F.1.2 [parallelism and concurrency]}
}

@Article{TemperoL95,
title={Recoverable Sequence Transmission Protocols},
author={Ewan D. Tempero and Richard E. Ladner},
pages={1059--1090},
area={Distributed Computing},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Theory},
keywords={Non-FIFO, protocol, sequence transmission},
cr-categories={C.2.2 [network protocols]; F.0 [general]}
}

@Article{Kahale95,
title={Eigenvalues and Expansion of Regular Graphs},
author={Nabil Kahale},
pages={1091--1106},
area={Graph Theory and Combinatorial Structures},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Algorithms, Theory},
keywords={Eigenvalues, expander graphs, induced subgraphs, load
balancing, Ramanujan graphs, random walks, selection networks},
cr-categories={F.2.2; G.2.2},
preliminary={FOCS::Kahale1991, FOCS::Kahale1992}
}

@Article{ConfortiC95,
title={A Class of Logic Problems Solvable by Linear Programming},
author={Michel Conforti and G{\'e}rard Cornu{\'e}jols},
pages={1107--1113},
area={Operations Research},
journal=jacm,
month=sep,
year=1995,
volume=42,
number=5,
general-terms={Algorithms},
keywords={Balanced matrices, linear programming, propositional logic},
cr-categories={F.2.2 [computations on discrete structures]; G.2.1
[combinatorial algorithms]}
}

                         Volume 42, Number 6
                            November 1995

@Article{GoemansW95,
title={Improved Approximation Algorithms for Maximum Cut and
Satisfiability Problems Using Semidefinite Programming},
author={Michel X. Goemans and David P. Williamson},
area={Complexity of Algorithms},
journal=jacm,
pages={1115--1145},
month=nov,
year=1995,
volume=42,
number=6,
general-terms={Algorithms},
keywords={Approximation algorithms, convex optimization, randomized
algorithms, satisfiability},
cr-categories={F.2.2 [computations on discrete structures]; G.2.2
[graph algorithms]; G.3 [probabilistic algorithms (including Monte
Carlo)]; I.1.2 [analysis of algorithms]},
preliminary={STOC::GoemansW1994}
}

@Article{FreivaldsKS95,
title={On the Impact of Forgetting on Learning Machines},
author={R{\=u}si{\c{n}}{\v{s}} Freivalds and Efim Kinber and Carl H.
Smith},
area={Computational Learning Theory},
journal=jacm,
pages={1146--1168},
month=nov,
year=1995,
volume=42,
number=6,
general-terms={machine learning, memory limited learning, inductive
inference, Kolmogorov complexity},
keywords={probabilistic automata, pumping lemma, recursion theorem},
cr-categories={F.1.1 [automata, relations among models,
unbounded-action devices]; F.1.2 [probabilistic computation]; F.1.3
[complexity hierarchies]; F.4.1 [recursive function theory]; I.2.6
[induction, concept learning]}
}

@Article{BoyarBP95,
title={Subquadratic Zero-Knowledge},
author={Joan Boyar and Gilles Brassard and Ren{\'e} Peralta},
area={Cryptology},
journal=jacm,
pages={1169--1193},
month=nov,
year=1995,
volume=42,
number=6,
general-terms={Algorithms, Security, Theory},
keywords={Bit commitment, circuit evaluation, communication
complexity, cryptography, interactive proofs, matrix multiplication,
non-averaging sets, probabilistic algorithms, proof systems,
randomness, zero knowledge},
cr-categories={C.2.0 [security and protection]; D.4.6 [cryptographic
controls]; E.3; F.0; F.1.2 [alternation and nondeterminism \and
interactive computation \and probabilistic computation]; F.1.3; F.2.1
[computations on matrices]; F.2.2 [complexity of proof procedures \and
computations on discrete structures]; F.2.3; F.4.1 [proof theory]; G.3
[probabilistic algorithms]; K.4.1 [privacy]},
preliminary={FOCS::BoyarBP1991}
}

@Article{BergstraT95,
title={Equational Specifications, Complete Term Rewriting Systems, and
Computable and Semicomputable Algebras},
author={J. A. Bergstra and J. V. Tucker},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
pages={1194--1230},
month=nov,
year=1995,
volume=42,
number=6,
general-terms={Languages, Theory},
keywords={Abstract data types, complete term rewriting systems,
computable and semicomputable algebras, equational specifications with
hidden functions, many sorted algebras, term rewriting systems},
cr-categories={D.3.3; F.1.1; F.3.2; F.3.3; F.4.1}
}

@Article{AfekGMT95,
title={Computing with Faulty Shared Ojects},
author={Yehuda Afek and David S. Greenberg and Michael Merritt and
Gadi Taubenfeld},
area={Distributed Computing},
journal=jacm,
pages={1231--1274},
month=nov,
year=1995,
volume=42,
number=6,
general-terms={Algorithms, fault-tolerance, shared memory,
synchronization},
keywords={Atomic operations},
cr-categories={B.3.2 [shared memory]}
}

@Article{ToyamaKB95,
title={Termination for Direct Sums of Left-Linear Complete Term
Rewriting Systems},
author={Y. Toyama and Jan Willem Klop and H. P. Barendregt},
area={Programming Languages and Methodology},
journal=jacm,
pages={1275--1304},
month=nov,
year=1995,
volume=42,
number=6,
general-terms={Theory},
keywords={Confluence, left-linearity, term rewriting systems},
cr-categories={F.4.2}
}

                         Volume 43, Number 1
                             January 1996

@Article{AfekAPS96,
title={Local Management of a Global Resource in a Communication
Network},
author={Yehuda Afek and Baruch Awerbuch and Serge Plotkin and Michael
Saks},
area={Complexity of Algorithms},
journal=jacm,
pages={1--19},
month=jan,
year=1996,
volume=43,
number=1,
general-terms={Algorithms, Theory},
keywords={Diffusing computations, distributed computation, distributed
network management, resource management},
cr-categories={C.2.3; C.2.4; F.2.2; G.2.2},
preliminary={FOCS::AfekAPS1987:347}
}

@Article{ChenW96,
title={Tabled Evaluation with Delaying for General Logic Programs},
author={Weidong Chen and David S. Warren},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
pages={20--74},
month=jan,
year=1996,
volume=43,
number=1,
general-terms={Query Evaluation, Deductive Databases, Logic
Programming},
keywords={Program transformations, stable models, tabled evaluation,
well-founded models},
cr-categories={F.4.1[logic programming \and proof theory]; H.2.3[query
languages]; H.2.4[query processing]; I.2.3[logic programming \and
Nonmonotonic reasoning and belief revision]},
preliminary={PODS::ChenW1993}
}

@Article{JoungS96,
title={A Comprehensive Study of the Complexity of Multiparty
Interaction},
author={Yuh-Jzer Joung and Scott A. Smolka},
area={Distributed Computing},
journal=jacm,
pages={75--115},
month=jan,
year=1996,
volume=43,
number=1,
general-terms={Languages, Design, Theory},
keywords={Distributed languages, multiparty interaction, multiparty
interaction scheduling, taxonomy},
cr-categories={D.1.3; D.3.2[concurrent, distributed, and parallel
languages]; D.3.3[concurrent programming structures \and
input/output]; D.4.1[synchronization]; D.4.4[input/output];
D.4.7[distributed systems]; F.2.3},
preliminary={POPL::JoungS1992:142}
}

@Article{AlurFH96,
title={The Benefits of Relaxing Punctuality},
author={Rajeev Alur and Tom{\'a}s Feder and Thomas A. Henzinger},
area={Logic in Computer Science},
journal=jacm,
pages={116--146},
month=jan,
year=1996,
volume=43,
number=1,
general-terms={Theory, Verification},
keywords={Model checking, real time, temporal logic, timed automata},
cr-categories={D.3[real-time systems]; D.2.1[languages]; F.3.1[logics
of programs \and mechanical verification \and specification
techniques]; F.4.3[classes defined by automata \and decision
problems]}
}

@Article{MiltersenPT96,
title={The Asymptotic Complexity of Merging Networks},
author={Peter Bro Miltersen and Mike Paterson and Jun Tarui},
area={Parallel Computation},
journal=jacm,
pages={147--165},
month=jan,
year=1996,
volume=43,
number=1,
general-terms={Algorithms, Theory},
keywords={Comparator network, merging, sorting},
cr-categories={F.2.2[sorting and searching]},
preliminary={FOCS::MiltersenPT1992:236}
}

@Article{BoyerY96,
title={Automated Proofs of Object Code for a Widely Used
Microprocessor},
author={Robert S. Boyer and Yuan Yu},
area={Programming Languages and Methodology},
journal=jacm,
pages={166--192},
month=jan,
year=1996,
volume=43,
number=1,
general-terms={Theory},
keywords={Ada, automated reasoning, Boyer-Moore logic, C, Common Lisp,
formal methods, machine code, mechanical theorem proving, MC68xxx,
Nqthm, object code, program proving, program verification},
cr-categories={D.2.1; D.2.4; D.3.1; F.3.1; I.2.3}
}

                         Volume 43, Number 2
                              March 1996

@Article{SelmanKS96,
title={Knowledge Compilation and Theory Approximation},
author={Bart Selman and Henry Kautz},
area={Artificial Intelligence},
journal=jacm,
pages={193--224},
month=mar,
year=1996,
volume=43,
number=2,
general-terms={Algorithms, Experimentation, Theory},
keywords={Efficient reasoning methods, Horn clauses, knowledge-based
optimization, knowledge compilation, query evaluation, theory
approximations},
cr-categories={F.4.1; I.2.3; I.2.4}
}

@Article{ChandraT96,
title={Unreliable Failure Detectors for Reliable Distributed Systems},
author={Tushar Deepak Chandra and Sam Toueg},
area={Distributed Computing},
journal=jacm,
pages={225--267},
month=mar,
year=1996,
volume=43,
number=2,
general-terms={Algorithms, Reliability, Theory},
keywords={agreement problem, asynchronous systems, atomic broadcast,
\emph{Byzantine Generals'} problem, commit problem, consensus problem,
crash failures, failure detection, fault-tolerance, message passing,
partial synchrony, processor failures},
cr-categories={C.2.4 [distributed applications \and distributed
databases \and network operating systems]; C.4 [reliability,
availability, and serviceability]; D.1.3 [distributed programming];
D.4.5 [fault-tolerance]; F.1.1 [automata \and relations among models];
F.1.2 [parallelism and concurrency]; H.2.4 [concurrency \and
distributed systems \and transaction processing]}
}

@Article{FeigeGLSS96,
title={Interactive Proofs and the Hardness of Approximating Cliques},
author={Uriel Feige and Shafi Goldwasser and Laszlo Lov{\'a}sz and
Shmuel Safra and Mario Szegedy},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={268--292},
month=mar,
year=1996,
volume=43,
number=2,
general-terms={Algorithms, Theory},
keywords={Hardness of approximation, independent set in a graph,
multilinearity testing, \emph{np-completeness}, probabilistically
checkable proofs},
cr-categories={F.1.3[reducibility and completeness \and relations
among complexity classes]; F.2.2; G.2.2}
}

@Article{BhattCHLORS96,
title={Optimal Emulations by Butterfly-Like Networks},
author={Sandeep N. Bhatt and Fan R. K. Chung and Jia-Wei Hong and F.
Thomson Leighton and Bojana Obreni{\'c} and Arnold L. Rosenberg and
Eric J. Schwabe},
journal=jacm,
pages={293--330},
month=mar,
year=1996,
volume=43,
number=2,
area={Parallel Computation},
general-terms={Algorithms, Design, Theory},
keywords={Embeddings, emulations, mapping algorithms, mapping
problems, parallel architectures, processor arrays},
cr-categories={C.1.2 [interconnection architectures]; F.2.2
[Computations on discrete structures]; G.2.1 [combinatorial
algorithms]; G.2.2 [graph algorithms]}
}

@Article{GoodrichK96,
title={Sorting on a Parallel Pointer Machine with Applications to Set
Expression Evaluation},
author={Michael T. Goodrich and S. Rao Kosaraju},
area={Parallel Computation},
journal=jacm,
pages={331--361},
month=mar,
year=1996,
volume=43,
number=2,
general-terms={Algorithms, Theory, Verification},
keywords={Cascade merging, expression evaluation, linking automaton,
mergesort, parallel algorithms, pointer machine, PRAM},
cr-categories={E.1[arrays \and lists]; F.2.2[sorting and searching]},
preliminary={FOCS::GoodrichK1989:190}
}

@Article{CurienHL96,
title={Confluence Properties of Weak and Strong Calculi of Explicit
Substitutions},
author={Pierre-Louis Curien and Th{\'e}r{\`e}se Hardin and
Jean-Jacques L{\'e}vy},
area={Programming Languages and Methodology},
journal=jacm,
pages={362--397},
month=mar,
year=1996,
volume=43,
number=2,
general-terms={Languages, Theory},
keywords={Confluency, explicit substitutions},
cr-categories={F.3.2[operational semantics]; F.3.3[functional
constructs]; F.4.1[lambda calenders and related systems]}
}

                         Volume 43, Number 3
                               May 1996

@Article{Santos96,
title={On Linear Potential Functions for Approximating {Bayesian}
Computations},
author={Santos, Jr., Eugene},
area={Artificial Intelligence},
journal=jacm,
pages={399--430},
month=may,
year=1996,
volume=43,
number=3,
general-terms={Algorithms, Design, Experimentation, Theory},
keywords={Artificial intelligence, data compaction and compression,
integer programming, least squares approximation, pattern recognition,
probabilistic reasoning, uncertainty},
cr-categories={E.4; G.1.2; G.1.6; I.2.3; I.5}
}

@Article{GoldreichO96,
title={Software Protection and Simulation on Oblivious {RAMs}},
author={Oded Goldreich and Rafail Ostrovsky},
area={Cryptology},
journal=jacm,
pages={431--473},
month=may,
year=1996,
volume=43,
number=3,
general-terms={Security, Theory},
keywords={Pseudorandom functions, simulation of random access
machines, software protection},
cr-categories={C.2.0; E.3; F.1.1[bounded-action devices]},
preliminary={STOC::Goldreich1987, STOC::Ostrovsky1990}
}

@Article{MarcusS96,
title={Foundations of Multimedia Database Systems},
author={Sherry Marcus and V. S. Subrahmanian},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
pages={474--523},
month=may,
year=1996,
volume=43,
number=3,
general-terms={Languages, Theory},
keywords={Data structures, multimedia databases, query languages,
query processing},
cr-categories={F.4.1; H.2.3; H.2.5}
}

@Article{NederhofB96,
title={Linear-Time Suffix Parsing for Deterministic Languages},
author={Mark-Jan Nederhof and Eberhard Bertsch},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={524--554},
month=may,
year=1996,
volume=43,
number=3,
general-terms={Theory, Verification},
cr-categories={D.3.4[parsing]; F.4.2[parsing]}
}

@Article{GlabbeekW96,
title={Branching Time and Abstraction in Bisimulation Semantics},
author={Rob J. van Glabbeek and W. Peter Weijland},
area={Logic in Computer Science},
journal=jacm,
pages={555--600},
month=may,
year=1996,
volume=43,
number=3,
keywords={Abstraction, action refinement, bisimulation, branching
time, concurrency, process algebra, semantic equivalence},
cr-categories={D.3.1; F.1.2; F.3.2; F.4.3}
}

                         Volume 43, Number 4
                              July 1996

@Article{KargerS96,
title={A New Approach to the Minimum Cut Problem},
author={David R. Karger and Clifford Stein},
area={Complexity of Algorithms},
journal=jacm,
pages={601--640},
month=jul,
year=1996,
volume=43,
number=4,
keywords={Graph algorithm, minimum cut, network reliability, parallel
computing, randomized algorithm},
cr-categories={F.2.2; G.2.2[graph algorithms \and network problems];
G.3[probabilistic algorithms (including Monte Carlo)]; I.1.2},
general-terms={Algorithms}
}

@Article{ChengM96,
title={Bounding Errors Introduced by Clustering of Customers in Closed
Product--Form Queueing Networks},
author={William C. Cheng and Richard R. Muntz},
area={Computer System Modeling and Analysis},
journal=jacm,
pages={641--669},
month=jul,
year=1996,
volume=43,
number=4,
keywords={Balance equation, closed network, clustering, error bound,
product--form, quasi-reversibility, queuing network},
cr-categories={C.4; D.4.8[queuing theory]; G.m},
general-terms={Algorithms, Theory}
}

@Article{KoscielskiP96,
title={Complexity of {Makanin's} Algorithm},
author={Antoni Ko{\'s}cielski and Leszek Pacholski},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
pages={670--684},
month=jul,
year=1996,
volume=43,
number=4,
keywords={Diophantine equation, periodicity, semantic unification,
semigroups, word equations},
cr-categories={F.2.2[computations on discrete structures];
I.1.2[algebraic algorithms]},
general-terms={Algorithms, complexity, equations},
preliminary={FOCS::KoscielskiP1996}
}

@Article{ChandraHT96,
title={The Weakest Failure Detector for Solving {Consensus}},
author={Tushar Deepak Chandra and Vassos Hadzilacos and Sam Toueg},
area={Distributed Computing},
journal=jacm,
pages={685--722},
month=jul,
year=1996,
volume=43,
number=4,
keywords={agreement problem, asynchronous systems, atomic broadcast,
\emph{Byzantine Generals'} problem, commit problem, consensus problem,
crash failures, failure detection, fault-tolerance, message passing,
partial synchrony, processor failures},
cr-categories={C.2.4[distributed applications \and distributed
databases \and network operating systems]; C.4[reliability,
availability, and serviceability]; D.1.3[distributed programming];
D.4.5[fault-tolerance]; F.1.1[automata \and relations among models];
F.1.2[parallelism and concurrency]; H.2.4[concurrency \and distributed
systems  \and transaction processing]},
general-terms={Algorithms, Reliability, Theory}
}

@Article{LiTV96,
title={How to Share Concurrent Wait-Free Variables},
author={Ming Li and John Tromp and Paul M. B. Vit{\'a}nyi},
area={Distributed Computing},
journal=jacm,
pages={723--746},
month=jul,
year=1996,
volume=43,
number=4,
keywords={Atomicity, concurrent reading and writing, multi-writer,
shared variable (register)},
cr-categories={B.3.2; B.4.3; D.4.1; D.4.4},
general-terms={Management}
}

@Article{BshoutyT96,
title={On the {Fourier} Spectrum of Monotone Functions},
author={Nader H. Bshouty and Christino Tamon},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={747--770},
month=jul,
year=1996,
volume=43,
number=4,
keywords={Approximation, circuits, complexity, Fourier transform,
functions, harmonic analysis learning, monotone Boolean, monotone
circuits},
cr-categories={F.1.2[probabilistic computation]; F.2.1[computation of
transforms \and computation on polynomials]; G.3[probabilistic
algorithms]; I.2.6[concept learning]},
general-terms={Algorithms, Theory}
}

                         Volume 43, Number 5
                            September 1996

@Article{VitterK96,
title={Optimal Prefetching via Data Compression},
author={Jeffrey Scott Vitter and P. Krishnan},
area={Data Structures and Analysis of Algorithms},
journal=jacm,
pages={771--793},
month=sep,
year=1996,
volume=43,
number=5,
keywords={Caching, competitive analysis, databases, data compression,
fault rate, hypertext, Markov source, prediction, prefetching,
secondary stage, universal prefetcher},
general-terms={Algorithms, design, performance, theory},
cr-categories={D.4.2[swapping, virtual memory]; D.4.8[stochastic
analysis]; E.4[data compaction and compression]; I.2.6},
preliminary={focs::VitterK1991}
}

@Article{BuschM96,
title={A Combinatorial Treatment of Balancing Networks},
author={Costas Busch and Marios Mavronicolas},
area={Distributed Computing},
journal=jacm,
pages={794--839},
month=sep,
year=1996,
volume=43,
number=5,
keywords={Balancing networks, block-input networks, block-output
networks, combinatorial characterizations, counting networks,
impossibility results, incidence matrices, smoothing networks,
transfer parameters },
general-terms={Theory, Verification, Algorithms},
cr-categories={C.2.1[distributed networks \and network topology];
C.2.4[distributed applications]; F.1.2[parallelism and concurrency];
F.2.2[sorting and searching]; G.2.1[combinatorial algorithms \and
counting problems]; G.2.2[graph algorithms \and networks problems]},
preliminary={PODC::BuschM1994:206}
}

@Article{HellersteinPRW96,
title={How Many Queries are Needed to Learn?},
author={Lisa Hellerstein and Krishnan Pillaipakkamnatt and Vijay
Raghavan and Dawn Wilkins},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={840--862},
month=sep,
year=1996,
volume=43,
number=5,
general-terms={Algorithms, Design, Theory},
cr-categories={F.1.1[relations among models]; F.1.2[relativized
computation \and interactive computation]; F.1.3[complexity
hierarchies]; I.2.6[concept learning \and induction]},
keywords={Certificates, equivalence queries, exact identification,
membership queries, polynomial-time hierarchy, polynomial-time
learning, polynomial-query learning, proper learning}
}

@Article{BolG96,
title={The Meaning of Negative Premises in Transition System
Specifications},
author={Roland Bol and Jan Friso Groote},
area={Programming Languages and Methodology},
journal=jacm,
pages={863--914},
month=sep,
year=1996,
volume=43,
number=5,
general-terms={Algebra, Semantics},
cr-categories={D.3.1; F.3.1; F.3.2; I.2.3},
keywords={Bisimulation, congruence, conservative extension of TSSs,
logic programming, negative premises, \emph{ntyft/ntyxt}-format,
priorities and abstraction, process algebra}
}

                         Volume 43, Number 6
                            November 1996

@Article{Baeza-YatesG96,
title={Fast Text Searching for Regular Expressions or Automaton
Searching on Tries},
author={Ricardo A. Baeza-Yates and Gaston H. Gonnet},
area={Analysis of Algorithms},
journal=jacm,
pages={915--936},
month=nov,
year=1996,
volume=43,
number=6,
general-terms={Algorithms},
cr-categories={E.1; F.2; H.3.3; I.5.4[text processing]},
keywords={Digital trees, finite automata, regular expressions, text
searching}
}

@Article{OmlinG96,
title={Constructing Deterministic Finite-State Automata in Recurrent
Neural Networks},
author={Christian W. Omlin and C. Lee Giles},
area={Artificial Intelligence},
journal=jacm,
pages={937--972},
month=nov,
year=1996,
volume=43,
number=6,
general-terms={Algorithms, Theory, Verification},
cr-categories={B.2.2[simulation \and verification]; F.1.1[automata
\and relations among models \and self-modifying machine];
G.1.0[stability]; G.1.2[nonlinear approximation];
I.2.4[representations]; I.5.1[neural nets]},
keywords={Automata, connectionism, knowledge encoding, neural
networks, nonlinear dynamics, recurrent neural networks, rules,
stability}
}

@Article{AggarwalBCRSS96,
title={Efficient Routing in Optical Networks},
author={Alok Aggarwal and Amotz Bar-Noy and Don Coppersmith and Rajiv
Ramaswami and Baruch Schieber and Madhu Sudan},
area={Communication Networks},
journal=jacm,
pages={973--1001},
month=nov,
year=1996,
volume=43,
number=6,
general-terms={Algorithms},
cr-categories={F.2.2; G.2.1; G.2.2},
keywords={Optical networks, routing, wavelength assignment},
preliminary={soda::AggarwalBCRSS1994}
}

@Article{BasuPR96,
title={On the Combinatorial and Algebraic Complexity of Quantifier
Elimination},
author={Saugata Basu and Richard Pollack and Marie-Fran{\c{c}}oise
Roy},
area={Complexity of Algorithms},
journal=jacm,
pages={1002--1045},
month=nov,
year=1996,
volume=43,
number=6,
general-terms={Algorithms, Theory},
cr-categories={F.4.3[decision problems]},
keywords={Quantifier elimination, real closed fields,
Tarski-Seidenberg principle}
}

@Article{SippuS96,
title={An Analysis of Magic Sets and Related Optimization Strategies
for Logic Queries},
author={Seppo Sippu and Eljas Soisalon-Soininen},
area={Database Theory},
journal=jacm,
pages={1046--1088},
month=nov,
year=1996,
volume=43,
number=6,
general-terms={Algorithms, Languages, Theory},
cr-categories={H.2.4[query processing]; I.2.3[logic programming]},
keywords={Datalog, envelopes, logic query, magic sets},
preliminary={icde::SippuS1988, icdt::SippuS1990}
}

                         Volume 44, Number 1
                             January 1997

@Article{MillerTTV1997,
title={Separators for Sphere-Packings and Nearest Neighbor Graphs},
author={Gary L. Miller and Shang-Hua Teng and William Thurston and
Stephen A. Vavasis},
area={Computational Geometry},
journal=jacm,
pages={1--29},
month=jan,
year=1997,
volume=44,
number=1,
general-terms={Algorithms, Theory},
cr-categories={E.1[graphs \and trees]; F.2.1[computation of
transforms]; F.2.2[computaions on discrete structures \and geometrical
problems and computations \and sorting and searching]; G.2.1;
G.2.2[graph algorithms \and trees]; G.3[probabilistic algorithms \and
random number generation]; G.4[algorithm analysis \and efficiency]},
keywords={Centerpoint, computational geometry, graph algorithms, graph
separators, partitioning, probabilistic method, point location,
randomized algorithm, sphere-preserving mapping}
}

@Article{AbiteboulVV1997,
title={Fixpoint Logics, Relational Machines, and Computational
Complexity},
author={Serge Abiteboul and Moshe Y. Vardi and Victor Vianu},
area={Database Theory},
journal=jacm,
pages={30--56},
month=jan,
year=1997,
volume=44,
number=1,
general-terms={Algorithms, Theory},
cr-categories={F.1.1[bounded-action devices \and random access
machines \and computability theory \and relations among models];
F.1.3[relations among complexity classes \and relations among
complexity measures]; F.4.1[computational logic]; H.2.3[query
languages]},
keywords={Complexity classes, computational complexity, fixpoint
logic, relational complexity}
}

@Article{Morishita1997,
title={Avoiding {Cartesian} Products for Multiple Joins},
author={Shinichi Morishita},
area={Database Theory},
journal=jacm,
pages={57--85},
month=jan,
year=1997,
volume=44,
number=1,
general-terms={Algorithms, Database Theory, Languages},
cr-categories={F.2.2[sequencing and scheduling]; H.2.4[query
processing]; I.2.8[plan execution \and formation generation]},
keywords={Cartesian product, database scheme, join expression tree,
join strategy, optimality, semijoin},
preliminary={pods::Morishita1992}
}

@Article{AwerbuchS1997,
title={The Maintenance of Common Data in a Distributed System},
author={Baruch Awerbuch and Leonard J. Schulman},
area={Distributed Computing},
journal=jacm,
pages={86--103},
month=jan,
year=1997,
volume=44,
number=1,
general-terms={Algorithms, Databases},
cr-categories={C.2.1; C.2.2; C.2.4; D.4.3; H.2.4},
keywords={Distributed computing, distributed databases, network
management, network topology update, routing}
}

@Article{KochLMRRS1997,
title={Work-Preserving Emulations of Fixed-Connection Networks},
author={Richard R. Koch and F. T. Leighton and Bruce M. Maggs and
Satish B. Rao and Arnold L. Rosenberg and Eric J. Schwabe},
area={Parallel Computation},
journal=jacm,
pages={104--147},
month=jan,
year=1997,
volume=44,
number=1,
general-terms={Algorithms, Design, Theory},
cr-categories={C.1.2[parallel processors]; C.2.1[network topology];
F.1.1[networks of machines]; F.2.2[computations on discrete
structures]; G.2.1[combinatorial algorithms]; G.2.2[graph
algorithms]},
keywords={Graph embeddings, network emulations, parallel
architectures, processors arrays},
preliminary={STOC::KochLMRR1989:227},
}

@Article{IshiiLP1997,
title={Optimizing Two-Phase, Level-Clocked Circuitry},
author={Alexander T. Ishii and Charles E. Leiserson and Marios C.
Papaefthymiou},
area={VLSI Computation and Design},
journal=jacm,
pages={148--199},
month=jan,
year=1997,
volume=44,
number=1,
general-terms={Algorithms, Design},
cr-categories={B.6.3[optimization, verification]; B.7; F.2},
keywords={Clock tuning, level-clocked circuitry, multiphase clocking,
retiming, timing analysis and optimization, VLSI}
}

                         Volume 44, Number 2
                              March 1997

@Article{BistarelliMR1997,
title={Semiring-Based Constraint Satisfaction and Optimization},
author={Stefano Bistarelli and Ugo Montanari and Francesca Rossi},
area={Artificial Intelligence},
journal=jacm,
pages={201--236},
month=mar,
year=1997,
volume=44,
number=2,
general-terms={},
cr-categories={},
keywords={}
}

@Article{JiangSV1997:237,
title={Two Heads Are Better than Two Tapes},
author={Tao Jiang and Joel I. Seiferas and Paul M. B. Vit{\'a}nyi},
area={Complexity of Algorithms},
journal=jacm,
pages={237--256},
month=mar,
year=1997,
volume=44,
number=2,
general-terms={},
cr-categories={},
keywords={},
preliminary={STOC::JiangSV1994}
}

@Article{FrandsenMS1997,
title={Dynamic Word Problems},
author={Gudmund Skovbjerg Frandsen and Peter Bro Miltersen and Sven
Skyum},
area={Complexity of Algorithms},
journal=jacm,
pages={257--271},
month=mar,
year=1997,
volume=44,
number=2,
general-terms={},
cr-categories={},
keywords={},
preliminary={FOCS::FrandsenMS1993:470}
}

@Article{BusscheGAG1997,
title={On the Completeness of Object-Creating Database Transformation
Languages},
author={Jan Van den Bussche and Dirk Van Gucht and Marc Andries and
Marc Gyssens},
area={Database Theory},
journal=jacm,
pages={272--319},
month=mar,
year=1997,
volume=44,
number=2,
general-terms={},
cr-categories={},
keywords={},
preliminary={focs::BusscheGAG1992:372}
}

@Article{BibelE1997,
title={Decomposition of Tautologies into Regular Formulas and Strong
Completeness of Connection-Graph Resolution},
author={W. Bibel and E. Eder},
area={Deductive Systems and Equational Reasoning},
journal=jacm,
pages={320--344},
month=mar,
year=1997,
volume=44,
number=2,
general-terms={},
cr-categories={},
keywords={}
}

@Article{Wagner1997,
title={Evaluating Uniform Expressions Within Two Steps of Minimum
Parallel Time},
author={Robert A. Wagner},
area={Parallel Computation},
journal=jacm,
pages={345--361},
month=mar,
year=1997,
volume=44,
number=2,
general-terms={},
cr-categories={},
keywords={}
}

                         Volume 44, Number 3
                               May 1997

@Article{Halpern1997,
title={On Becoming Editor-in-Chief of~{JACM}},
author={Joe Halpern},
journal=jacm,
pages={363--365},
month=may,
year=1997,
volume=44,
number=3
}

@Article{LiuNT1997,
title={Exponential Bounds with Applications to Call Admission},
author={Zhen Liu and Philippe Nain and Don Towsley},
area={Computer System Modeling and Analysis},
journal=jacm,
pages={366--394},
month=may,
year=1997,
volume=44,
number=3,
general-terms={Performance, Theory},
cr-categories={C.2.0; C.4[modeling techniques]; G.m[queuing theory];
I.6.5},
keywords={Call admission control, effective bandwidth, ergodicity,
exponential bound, large deviation principle, Markov additive process,
Markov chain, matrix analysis, queues, tail distribution}
}

@Article{MohringMW1997,
title={Mesh Refinement via Bidrected Flows: Modeling, Complexity, and
Computational Results},
author={Rolf H. M{\"o}hring and Matthias M{\"u}ller-Hannemann and
Karsten Weihe},
area={Computing in Technology and the Sciences},
journal=jacm,
pages={395--426},
month=may,
year=1997,
volume=44,
number=3,
general-terms={Algorithms, design, experimentation},
cr-categories={F.2.2[computations on discrete structures]; G.2.2[graph
algorithms \and network problems]; J.6},
keywords={Augmenting paths, $b$-matching problem, bidirected flows,
mesh generation, $\mathcal{NP}$-completeness, templates},
preliminary={soda::MohringMW1995:350}
}

@Article{Cesa-BianchiFHHSW1997,
title={How to Use Expert Advice},
author={Nicol{\`o} Cesa-Bianchi and Yoav Freund and David Haussler and
David P. Helmbold and Robert E. Schapire and Manfred K. Warmuth},
area={Formal Languages and Complexity Theory},
preliminary={stoc::Cesa-BianchiFHHSW1993},
journal=jacm,
pages={427--485},
month=may,
year=1997,
volume=44,
number=3,
general-terms={Algorithms},
cr-categories={I.2.1; I.2.[automatic analysis of algorithms];
I.2.6[knowledge acquisition}
}

@Article{AspnesAFPW1997,
title={On-Line Routing of Virtual Circuits with Applications to Load
Balancing and Machine Scheduling},
author={James Aspnes and Yossi Azar and Amos Fiat and Serge Plotkin
and Orli Waarts},
area={Operations Research},
journal=jacm,
pages={486--504},
month=may,
year=1997,
volume=44,
number=3,
general-terms={Algorithms, Theory},
cr-categories={C.2.1; F.2.2},
keywords={High-speed networks, on-line algorithms, optimization,
routing},
preliminary={stoc::AspnesAFPW1993:623}
}

@Article{SekarRM1997,
title={On the Power and Limitations of Strictness Analysis},
author={R. Sekar and I. V. Ramakrishnan and P. Mishra},
area={Programming Languages and Methodology},
journal=jacm,
pages={505--525},
month=may,
year=1997,
volume=44,
number=3,
general-terms={Languages, Theory, Measurement},
cr-categories={D.3.1; D.3.2[applicative languages]; D.3.4[compilers
\and optimization]},
keywords={Abstract interpretation, completness, program analysis,
strictness analysis},
preliminary={popl::SekarRM1991}
}

                         Volume 44, Number 4
                              July 1997

@Article{Jeavons1997,
title={Closure Properties of Constraints},
author={Peter Jeavons and David Cohen and Marc Gyssens},
area={Artificial Intelligence},
journal=jacm,
pages={527--548},
month=jul,
year=1997,
volume=44,
number=4,
general-terms={Algorithms, Languages, Theory, Verification},
cr-categories={F.1.3[reducibility and completeness]; F.2.2[complexity
of proof procedures]; F.4.1; G.2.1},
keywords={Complexity, constraint satisfaction problem, indicator
problem, NP-completeness}
}

@Article{BeekD1997,
title={Constraint Tightness and Looseness versus Local and Global
Consistency},
author={Peter van Beek and Rina Dechter},
area={Artificial Intelligence},
journal=jacm,
pages={549--566},
month=jul,
year=1997,
volume=44,
number=4,
general-terms={Algorithms, Theory},
cr-categories={F.2.2[computations on discrete structures];
G.2.1[permutations and combinatorics]; I.2.4[relation systems]},
keywords={Constraint-based reasoning, constraint networks, constraint
satisfaction problems, local consistency, relations}
}

@Article{AgarwalHSV1997,
title={Approximating Shortest Paths on a Convex Polytope in Three
Dimensions},
author={Pankaj K. Agarwal and Sariel Har-Peled and Micha Sharir and
Kasturi R. Varadarajan},
area={Computational Geometry},
journal=jacm,
pages={567--584},
month=jul,
year=1997,
volume=44,
number=4,
general-terms={Algorithms, Theory},
cr-categories={F.2.2[geometrical problems and computations]},
keywords={Approximation algorithms, convex polytopes, Euclidean
shortest paths}
}

@Article{StoerW1997,
title={A Simple Min-Cut Algorithm},
author={Mechthild Stoer and Frank Wagner},
area={Data Structures and Algorithms},
journal=jacm,
pages={585--591},
month=jul,
year=1997,
volume=44,
number=4,
general-terms={Algorithms},
cr-categories={G.1.2[graph algorithms]},
keywords={Min-Cut}
}

@Article{Jayanti1997,
title={Robust Wait-free Hierarchies},
author={Prasad Jayanti},
area={Distributed Computing},
journal=jacm,
pages={592--614},
month=jul,
year=1997,
volume=44,
number=4,
general-terms={Algorithms, Reliability, Theory},
cr-categories={B.3.2[shared memory]; B.4.3[asynchronous/synchronous
operation]; C.1.2[multiple-instruction stream, multiple-data stream
processor (MIMD)]; D.1.3; D.3.3[abstract data types, concurrent
programming stuctures]; D.4.1[concurrency,
multiprocessing/multiprogramming, synchronization]; D.4.7[distributed
systems]},
keywords={Asynchronous computing, hierarchy, implementation, MIMD,
robustness, shared memory, shared objects, synchronization,
wait-freedom},
preliminary={podc::Jayanti1993}
}

@Article{AlonBCH1997,
title={Scale-sensitive Dimensions, Uniform Convergence, and
Learnability},
author={Noga Alon and Shai Ben-David and Nicol{\`o} Cesa-Bianchi and
David Haussler},
area={Machine Learning and Computational Learning},
journal=jacm,
pages={616--631},
month=jul,
year=1997,
volume=44,
number=4,
cr-categories={I.2.6[concept learning]},
general-terms={Theory},
keywords={PAC learning, uniform laws of large numbers,
Vapnik-Chervonenkis dimension},
preliminary={FOCS::AlonBCH1993:292}
}

@Article{JiangSV1997:632,
title={Erratum: ``{Two} Heads Are Better than Two Tapes''},
author={Tao Jiang and Joel I. Seiferas and Paul M. B. Vit{\'a}nyi},
journal=jacm,
pages={632},
month=jul,
year=1997,
volume=44,
number=4
}

                         Volume 44, Number 5
                            September 1997

@Article{BrafmanLMS1997,
title={Applications of a Logic of Knowledge to Motion Planning under
Uncertainty},
author={Ronen I. Brafman and Jean-Claude Latombe and Yoram Moses and
Yoav Shoham},
area={Artificial Intelligence},
journal=jacm,
pages={633--668},
month=sep,
year=1997,
volume=44,
number=5,
keywords={Analysis, logics of knowledge and time, knowledge
representation, motion planning under uncertainty},
general-terms={Design, Theory},
cr-categories={I.2.9[motion planning under uncertainty];
I.2.4[epistemic logic]; F.3.1[optimal termination conditions}
}

@Article{EppsteinGIN1997,
title={Sparsification---A Technique for Speeding Up Dynamic Graph
Algorithms},
author={David Eppstein and Zvi Galil and Amnon Nissenzweig},
area={Data Structures and Analysis of Algorithms},
journal=jacm,
pages={669--696},
month=sep,
year=1997,
volume=44,
number=5,
keywords={Dynamic graph algorithms, minimum spanning trees, edge and
vertex connectivity},
general-terms={Algorithms},
cr-categories={F.2.2; G.2.2},
preliminary={focs::EppsteinGIN1992}
}

@Article{KhardonR1997,
title={Learning to Reason},
author={Roni Khardon and Dan Roth},
area={Machine Learning and Computational Learning},
journal=jacm,
pages={697--725},
month=sep,
year=1997,
volume=44,
number=5,
keywords={Common sense reasoning, computational learning, knowledge
representation, model-based reasoning},
general-terms={Algorithms, Theory},
cr-categories={I.2.3[deduction]; I.2.4; I.2.6[Knowledge acquisition]}
}

@Article{BorodinRSU1997,
title={How Much Can Hardware Help Routing?},
author={Allan Borodin and Prabhakar Raghavan and Baruch Schieber and
Eli Upfal},
area={Parallel Computation},
journal=jacm,
pages={726--741},
month=sep,
year=1997,
volume=44,
number=5,
keywords={Multi-port, packet routing, permutation routing, randomized
routing algorithms, single-port},
general-terms={Algorithms, Theory},
cr-categories={C.2.1; F.2.2; G.3}
}

@Article{Spencer1997,
title={Time-Work Tradeoffs for Parallel Algorithms},
author={Thomas H. Spencer},
area={Parallel Computation},
journal=jacm,
pages={742--778},
month=sep,
year=1997,
volume=44,
number=5,
keywords={Breadth first search, PRAM, nearby lists, shortest path,
topological sort, transitive colsure},
general-terms={Algorithms, Theory, Parallel Computation},
cr-categories={F.2.2[computations on discrete structures]; G.2.2[graph
algorithms]},
preliminary={soda::Spencer1991, spaa::spencer1991}
}

                         Volume 44, Number 6
                            November 1997

@Article{DworkHW1997,
title={Contention in Shared Memory Algorithms},
author={Cynthia Dwork and Maurice Herlihy and Orli Waarts},
area={Distributed Computing},
journal=jacm,
pages={779--805},
month=nov,
year=1997,
volume=44,
number=6,
keywords={Contention, counting networks, mutual exclusion},
general-terms={Algorithms, Theory},
cr-categories={F.2.m},
preliminary={stoc::DworkHW1993}
}

@Article{HemaspaandraHR1997,
title={Exact Analysis of {Dodgson} Elections: Lewis {Carroll's} 1876
Voting System Is Complete for Parallel Access to~{NP}},
author={Edith Hemaspaandra and Lane A. Hemaspaandra and J{\"o}rge
Rothe},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={806--825},
month=nov,
year=1997,
volume=44,
number=6,
keywords={Completeness, election sysstems, Lewis Carroll, majority
rule},
general-terms={Theory},
cr-categories={F.1.3; F.2.2; J.4},
preliminary={icalp::HemaspaandraHR1997:214}
}

@Article{WassermanB1997,
title={Software Reliability via Run-Time Result-Checking},
author={Hal Wasserman and Manuel Blum},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={826--849},
month=nov,
year=1997,
volume=44,
number=6,
keywords={Built-in testing, concurrent error detection, debugging,
fault tolerance, Fourier Transform, result-checking, self-correcting},
general-terms={Reliability, Algorithms, Verification},
cr-categories={D.2.5; F.2.1[Computation of transforms]; F.3.1},
preliminary={focs::BlumW1994:382}
}

@Article{Broy1997,
title={Compositional Refinement of Interactive Systems},
author={Manfred Broy},
area={Programming Languages and Methodology},
journal=jacm,
pages={850--891},
month=nov,
year=1997,
volume=44,
number=6,
keywords={Interactive systesm, refinement, specification},
general-terms={Design, Verification},
cr-categories={C.0; D.1.4; D.2.1[methodologies];
D.2.10[methodologies]; F.3.1[specification techniques]}
}

                         Volume 45, Number 1
                             January 1998

@Article{BenediktDLW1998,
title={Relational Expressive Power of Constraint Query Languages},
author={Michael Benedikt and Guozhu Dong and Leonid Libkin and Limsoon
Wong},
area={Database Theory},
journal=jacm,
pages={1--34},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Constraints, constraint query language, database, expressive
power, relational calculus},
general-terms={Languages, Theory},
cr-categories={F.4.1; H.2.3},
preliminary={pods::BenediktDLW1996}
}

@Article{FeketeKL1998,
title={Implementing Sequentially Consistent Shared Objects using
Broadcast and Point-to-Point Communication},
author={Alan Fekete and M. Frans Kaashoek and Nancy Lynch},
area={Distributed Computing},
journal=jacm,
pages={35--69},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Distributed shared memory, formal methods, input/output
automata, ordered multicast, Orca programming language, replicated
data},
general-terms={Algorithms, Verification},
cr-categories={C.2.2; C.2.4; D.4.7; F.3.1}
}

@Article{AroraS1998,
title={Probabilistic Checking of Proofs: A New Characterization
of~{NP}},
author={Sanjeev Arora and Shmuel Safra},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={70--122},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Approximation algorithms, complexity hierarchies,
computations on polynomials and finite fields, error-correcting codes,
hardness of approximations, interactive computation, NP-completeness,
probabilistic computation, proof checking, reducibility and
completeness, trade-offs/relations among complexity measures},
general-terms={Algorithms, Theory, Verification},
cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1},
preliminary={focs::AroraS1992}
}

@Article{SaksSZ1998,
title={Explicit {OR}-Dispersers with Polylogarithmic Degree},
author={Michael Saks and Aravind Srinivasan and Shiyu Zhou},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={123--154},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Derandomization, expander graphs, explicit constructions,
hashing lemmas, hardness of approximation, imperfect sources of
randomness, measures of information, pseudo-random generators,
randomized computation, time-space tradeoffs},
general-terms={Algorithms, Theory},
cr-categories={F.1.3[relations among randomized complexity classes];
G.2.1[combinatorial algorithms]; G.3[probabilistic algorithms]},
preliminary={stoc::SaksSZ1995}
}

@Article{SimaW1998,
title={Theory of Neuromata},
author={Ji{\v{r}}{\'\i} {\v{S}}{\'\i}ma and Ji{\v{r}}{\'\i}
Wiedermann},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={155--178},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Descriptional complexity, emptiness problem, finite neural
networks, Hopfield networks, regular expressions, string acceptors},
general-terms={Theory},
cr-categories={F.1.1[automata (e.g., finite, push-down,
resource-bounded) \and relations among models \and self-modifying
machines (e.g., neural networks)]; F.4.3 [classes defined by grammars
or automata (e.g., context-free languages, regular sets, recursive
sets) \and classes defined by resource-bounded automata \and decision
problems \and operations on languages]}
}

@Article{AndreevCR1998,
title={A New General Derandomization Method},
author={Alexander E. Andreev and Andrea E. F. Clementi and Jos{\'e}
D. P. Rolim},
area={Graph Theory and Combinatorial Structures},
journal=jacm,
pages={179--213},
month=jan,
year=1998,
volume=45,
number=1,
keywords={BPP, Boolean circuits, derandomization},
general-terms={Algorithms, Theory},
cr-categories={F.2.2[computations on discrete structures];
G.3[probabilistic algorithms]},
preliminary={icalp::AndreevCR1996}
}

@Article{FaginH1998,
title={Corrigendum: Reasoning about Knowledge and Probability},
author={Ronald Fagin and Joseph Y. Halpern},
journal=jacm,
pages={214},
month=jan,
year=1998,
volume=45,
number=1
}

                         Volume 45, Number 2
                              March 1998

@Article{DengKP1998,
title={How to Learn an Unknown Environment~{I}: The Rectilinear Case},
author={Xiaotie Deng and Tiko Kameda and Christos Papadimitriou},
area={Complexity of Algorithms},
journal=jacm,
pages={215--245},
month=mar,
year=1998,
volume=45,
number=2,
keywords={Competitive algorithms, computational geometry, gallery
tour, L1 metric, on-line algorithms, polygon with obstacles, shortest
path},
general-terms={Algorithms, Theory},
cr-categories={F.2.2}
}

@Article{KargerMS1998,
title={Approximate Graph Coloring by Semidefinite Programming},
author={David Karger and Rajeev Motwani and Madhu Sudan},
area={Complexity of Algorithms},
journal=jacm,
pages={246--265},
month=mar,
year=1998,
volume=45,
number=2,
keywords={Approximation algorithms, chromatic number, graph coloring,
NP-completeness, randomized algorithms},
general-terms={Algorithms, Optimization, Theory},
cr-categories={F.2.2; G.2.1; G.2.2}
}

@Article{DeyG1998,
title={Computing Homology Groups of Simplicial Complexes
in~{$\mathbf{R}^3$}},
author={Tamal K. Dey and Sumanta Guha},
area={Computational Geometry},
journal=jacm,
pages={266--287},
month=mar,
year=1998,
volume=45,
number=2,
keywords={$d$ dimensions, generators, homology, homotopy, simplicial
complexes, topology},
general-terms={Algorithms, Theory},
cr-categories={F.2.2; I.3.5},
preliminary={stoc::DeyG1996}
}

@Article{MartinezR1998,
title={Randomized Binary Search Trees},
author={Conrado Mart{\'\i}nez and Salvador Roura},
area={Data Structures and Analysis of Algorithms},
journal=jacm,
pages={288--323},
month=mar,
year=1998,
volume=45,
number=2,
keywords={Balanced trees, probablistic algebraic specification,
randomized data structures, search trees, self-organizing data
structures},
general-terms={Algorithms, Theory},
cr-categories={E.1; F2.},
preliminary={}
}

@Article{MacKenziePR1998,
title={On Contention Resolution Protocols and Associated Probabilistic
Phenomena},
author={P. D. Mackenzie and C. G. Plaxton and R. Rajaraman},
area={Parallel Computation},
journal=jacm,
pages={324--378},
month=mar,
year=1998,
volume=45,
number=2,
keywords={Parallel computation, hash functions, emulation protocols},
general-terms={Algorithms, Theory},
cr-categories={F.1.2[parallelism and concurrency]; F.2.2},
preliminary={stoc::MackenziePR1994}
}

                         Volume 45, Number 3
                               May 1998

@Article{Halpern1998,
title={Time to Publication: A Progress Report},
author={Joseph Y. Halpern},
area={Editorial},
journal=jacm,
pages={379--380},
month=may,
year=1998,
volume=45,
number=3
}

@Article{FernandesPS1998,
title={Efficient Descriptor-Vector Multiplications in Stochastic
Automata Networks},
author={Paulo Fernandes and Brigitte Plateau and William J. Stewart},
area={Computer System Modeling and Analysis},
journal=jacm,
pages={381--414},
month=may,
year=1998,
volume=45,
number=3,
keywords={Generalized tensor algebra, Markov chains, stochastic
automata networks, vector-descriptor multiplication},
general-terms={Algorithms, performance, theory},
cr-categories={C.4[modeling techniques]; G.1.3; G.3; I.6.5}
}

@Article{Aspnes1998,
title={Lower Bounds for Distributed Coin-Flipping and Randomized
Consensus},
author={James Aspnes},
area={Distributed Computing},
journal=jacm,
pages={415--450},
month=may,
year=1998,
volume=45,
number=3,
keywords={Consensus, impossibility, randomization},
general-terms={Reliability, Theory},
cr-categories={B.3.2[shared memory]; B.4.3[asynchronous/synchronous
operation]; C.1.2[multiple-instruction-stream, multiple-data-stream
processors (MIMD)]; D.1.3[distributed programming]; D.4.1[concurrency,
synchronization]; D.4.7[distributed systems]; F.2.m[miscellaneous]},
preliminary={stoc::Aspnes1997}
}

@Article{JayantiCT1998,
title={Fault-Tolerant Wait-Free Shared Objects},
author={Prasad Jayanti and Tushar Deepak Chandra and Sam Toueg},
area={Distributed Computing},
journal=jacm,
pages={451--500},
month=may,
year=1998,
volume=45,
number=3,
keywords={Asynchronous computing, fault-tolerance, implementation,
MIMD, shared memory, shared objects, synchronization},
general-terms={Algorithms, Reliability, Theory},
cr-categories={B.3.2[shared memory]; B.4.3[asynchronous/synchronous
operations]; C.1.2[multiple-instruction-stream, multiple-data-stream
processors (MIMD)]; D.1.3; D.3.3[abstract data types];
D.4.1[concurrency, multiprocessing/multiprogramming, synchronization];
D.4.7[distributed systems]}
}

@Article{AroraLMSS1998,
title={Proof Verification and the Hardness of Approximation Problems},
author={Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu
Sudan and Mario Szegedy},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={501--555},
month=may,
year=1998,
volume=45,
number=3,
keywords={NP-completeness, optimization, proof verification,
randomness},
general-terms={Algorithms, Theory},
cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1}
}