@article{Eiter-Gottlob/95,
AUTHOR = {Eiter, Thomas and Gottlob, Georg},
TITLE = {The complexity of logic-based abduction},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {3-42},
YEAR = {1995},
KEYWORDS = {abduction, complexity analysis, diagnosis, reasoning, propositional logic},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Nebel-Burckert/95,
AUTHOR = {Nebel, Bernhard and B{\"u}rckert, Hans-J{\"u}rgen},
TITLE = {Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {43-66},
YEAR = {1995},
KEYWORDS = {constraint satisfaction, interval algebra, qualitative reasoning, temporal reasoning},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Callahan-Kosaraju/95,
AUTHOR = {Callahan, Paul B. and Kosaraju, S. Rao},
TITLE = {A decomposition of multidimensional point sets with applications to $k$-nearest-neighbors and $n$-body potential fields},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {67-90},
YEAR = {1995},
KEYWORDS = {all nearest neighbors, fast multipole method},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Chien-Kim/95,
AUTHOR = {Chien, Andrew A. and Kim, Jae H.},
TITLE = {Planar-adaptive routing: Low-cost adaptive networks for multiprocessors},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {91-123},
YEAR = {1995},
KEYWORDS = {adaptive routing, fault tolerance, interconnection networks, multicomputers, packet routing, parallel processing, transmission-order preservation},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Attiya-Bar-Noy-Dolev/95,
AUTHOR = {Attiya, Hagit and Bar-Noy, Amotz and Dolev, Danny},
TITLE = {Sharing memory robustly in message-passing systems},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {124-142},
YEAR = {1995},
KEYWORDS = {atomic registers, emulation, fault-tolerance, message passing, processor and link failures, shared memory, wait-freedom},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Dolev-Halpern-Simons-Strong/95,
AUTHOR = {Dolev, Danny and Halpern, Joseph Y. and Simons, Barbara and Strong, Ray},
TITLE = {Dynamic fault-tolerant clock synchronization},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {143-185},
YEAR = {1995},
KEYWORDS = {Byzantine failures, clock synchronization, fault-tolerance, time-of-day clock},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Haldar-Vidyasankar/95a,
AUTHOR = {Haldar, S. and Vidyasankar, K.},
TITLE = {Constructing 1-writer multireader multivalued atomic variables from regular variables},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {186-203},
YEAR = {1995},
KEYWORDS = {nonatomic operation execution, reader and writer, shared-variable safe, regular and atomic, wait-freedom},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Chang-Nelson/95,
AUTHOR = {Chang, C.S. and Nelson, R.},
TITLE = {Bounds on the speedup and efficiency of partial synchronization in parallel processing systems},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {204-231},
YEAR = {1995},
KEYWORDS = {large deviations theory, synchronization},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bloom-Istrail-Meyer/95,
AUTHOR = {Bloom, Bard and Istrail, Sorin and Meyer, Albert R.},
TITLE = {Bisimulation can't be traced},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {232-268},
YEAR = {1995},
KEYWORDS = {bisimulation, structural operational semantics, process algebra, CCS},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Blum-Kannan/95,
AUTHOR = {Blum, Manuel and Kannan, Sampath},
TITLE = {Designing programs that check their work},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {1},
PAGES = {269-291},
YEAR = {1995},
KEYWORDS = {interactive proofs, probabilistic algorithms, program checking, program verification, testing},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lin-Shoham/95,
AUTHOR = {Lin, Fangzhen and Shoham, Yoav},
TITLE = {Provably correct theories of action},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {293-320},
YEAR = {1995},
KEYWORDS = {concurrent actions, the frame problem, reasoning about actions, temporal reasoning},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Karger-Klein-Tarjan/95,
AUTHOR = {Karger, David R. and Klein, Philip N. and Tarjan, Robert E.},
TITLE = {A randomized linear-time algorithm to find minimum spanning trees},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {321-328},
YEAR = {1995},
KEYWORDS = {matroid, minimum spanning tree, network, randomized algorithm},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Wang-Zhang-Chau/95,
AUTHOR = {Wang, Ke and Zhang, Weining and Chau, Siu-Cheung},
TITLE = {Decomposition of magic rewriting},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {329-381},
YEAR = {1995},
KEYWORDS = {arity reduction, bottom-up evaluation, database, deductive database, logic program, magic rewriting, program decomposition},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Tsitsiklis-Stamoulis/95,
AUTHOR = {Tsitsiklis, John N. and Stamoulis, George D.},
TITLE = {On the average communication complexity of asynchronous distributed algorithms},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {382-400},
YEAR = {1995},
KEYWORDS = {asynchronous distributed algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kurtz-Mahaney-Royer/95,
AUTHOR = {Kurtz, Stuart A. and Mahaney, Stephen R. and Royer, James S.},
TITLE = {The isomorphism conjecture fails relative to a random oracle},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {401-420},
YEAR = {1995},
KEYWORDS = {isomorphism, conjecture, randomness},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gottlob/95,
AUTHOR = {Gottlob, Georg},
TITLE = {NP trees and Carnap's modal logic},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {421-457},
YEAR = {1995},
KEYWORDS = {autoepistemic logic, bounded query computation, epistemic logic, modal logic, NP, oracle, trees},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{de_Nicola-Vaandrager/95,
AUTHOR = {de Nicola, Rocco and Vaandrager, Frits},
TITLE = {Three logics for branching bisimulation},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {458-487},
YEAR = {1995},
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},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Clarkson/95,
AUTHOR = {Clarkson, Kenneth L.},
TITLE = {Las Vegas algorithms for linear and integer programming when the dimension is small},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {488-499},
YEAR = {1995},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Berger-Brady-Brown-Leighton/95,
AUTHOR = {Berger, Bonnie and Brady, Martin and Brown, Donna and Leighton, Tom},
TITLE = {Nearly optimal algorithms and bounds for multilayer channel routing},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {2},
PAGES = {500-542},
YEAR = {1995},
KEYWORDS = {channel routing, multilayer routing, VLSI layout},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Choudhury-Leung-Whitt/95,
AUTHOR = {Choudhury, Gagan L. and Leung, Kin K. and Whitt, Ward},
TITLE = {Calculating normalization constants of closed queuing networks by numerically inverting their generating functions},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {935-970},
YEAR = {1995},
KEYWORDS = {closed queuing networks, dimension reduction, Euler summation, generating function, normalization constant, numerical transform inversion, partition function, performance analysis, production-form model, scaling},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Koutsoupias-Papadimitriou/95,
AUTHOR = {Koutsoupias, Elias and Papadimitriou, Christos H.},
TITLE = {On the $k$-server conjecture},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {971-983},
YEAR = {1995},
KEYWORDS = {competitive analysis, $k$-server problem, on-line algorithms, potential, quasiconvexity, work function},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Verma/95,
AUTHOR = {Verma, Rakesh M.},
TITLE = {A theory of using history for equational systems with applications},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {984-1020},
YEAR = {1995},
KEYWORDS = {congruence-closure algorithm, equational logic, rewrite systems, rewrite system transformation, proof theory, term rewriting},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Awerbuch-Peleg/95,
AUTHOR = {Awerbuch, Baruch and Peleg, David},
TITLE = {Online tracking of mobile users},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {1021-1058},
YEAR = {1995},
KEYWORDS = {bounded packet header, bounded protocol, ideal transmission cost, lookahead, non-FIFO channels, receiver-driven protocol, recoverable protocol, recovery cost, sequence transmission problem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Tempero-Ladner/95,
AUTHOR = {Tempero, Ewan D. and Ladner, Richard E.},
TITLE = {Recoverable sequence transmission protocols},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {1059-1090},
YEAR = {1995},
KEYWORDS = {non-FIFO, protocol, sequence transmission},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kahale/95,
AUTHOR = {Kahale, Nabil},
TITLE = {Eigenvalues and expansion of regular graphs},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {1091-1106},
YEAR = {1995},
KEYWORDS = {eigenvalues, expander graphs, induced subgraphs, load balancing, Ramanujan graphs, random walks, selection networks},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Conforti-Cornuejols/95,
AUTHOR = {Conforti, Michele and Cornu{\'e}jols, G{\'e}rard},
TITLE = {A class of logic problems solvable by linear programming},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {5},
PAGES = {1107-1113},
YEAR = {1995},
KEYWORDS = {balanced matrices, linear programming, propositional logic},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Goemans-Williamson/95a,
AUTHOR = {Goemans, Michel X. and Williamson, David P.},
TITLE = {Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {6},
PAGES = {1115-1145},
YEAR = {1995},
KEYWORDS = {approximation algorithms, convex optimization, randomized algorithms, satisfiability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Freivalds-Kinber-Smith/95a,
AUTHOR = {Freivalds, R{\=u}si{\c{n}}{\u{s}} and Kinber, Efim and Smith, Carl H.},
TITLE = {On the impact of forgetting on learning machines},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {6},
PAGES = {1146-1168},
YEAR = {1995},
KEYWORDS = {machine learning, memory limited learning, inductive inference, Kolmogorov complexity, probabilistic automata, pumping lemma, recursion theorem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Boyar-Brassard-Peralta/95,
AUTHOR = {Boyar, Joan and Brassard, Gilles and Peralta, Ren{\'e}},
TITLE = {Subquadratic zero-knowledge},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {6},
PAGES = {1169-1193},
YEAR = {1995},
KEYWORDS = {algorithms, security, theory, bit commitment, circuit evaluation, communication complexity, interactive proofs, matrix multiplication, non-averaging sets, probabilistic algorithms, proof systems, randomness, zero knowledge},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bergstra-Tucker/95,
AUTHOR = {Bergstra, J.A. and Tucker, J.V.},
TITLE = {Equational specifications, complete term rewriting systems, and computable and semicomputable algebras},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {6},
PAGES = {1194-1230},
YEAR = {1995},
KEYWORDS = {languages, theory, abstract data types, complete term rewriting systems, computable and semicomputable algebras, equational specifications with hidden functions, many sorted algebras, term rewriting systems},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Afek-Greenberg-Merritt-Taubenfeld/95,
AUTHOR = {Afek, Yehuda and Greenberg, David S. and Merritt, Michael and Taubenfeld, Gadi},
TITLE = {Computing with faulty shared objects},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {6},
PAGES = {1231-1274},
YEAR = {1995},
KEYWORDS = {algorithms, fault-tolerance, shared memory, synchronization, atomic operations},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Toyama-Klop-Barendregt/95,
AUTHOR = {Toyama, Y. and Klop, J.W. and Barendregt, H.P.},
TITLE = {Termination for direct sums of left-linear complete term rewriting systems},
JOURNAL = {J. ACM},
VOLUME = {42},
NUMBER = {6},
PAGES = {1275-1304},
YEAR = {1995},
KEYWORDS = {theory, confluence, left-linearity, term rewriting systems},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}