@article{Beame-Cook-Edmonds-Impagliazzo-Pitassi/98,
AUTHOR = {Beame, Paul and Cook, Stephen and Edmonds, Jeff and Impagliazzo, Russell and Pitassi, Toniann},
TITLE = {The relative complexity of $NP$ search problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {3-19},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Diaconis-Saloff-Coste/98,
AUTHOR = {Diaconis, P. and Saloff-Coste, L.},
TITLE = {What do we know about the metropolis algorithm?},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {20-36},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Miltersen-Nisan-Safra-Wigderson/98,
AUTHOR = {Miltersen, Peter Bro and Nisan, Noam and Safra, Shmuel and Wigderson, Avi},
TITLE = {On data structures and asymmetric communication complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {37-49},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kavraki-Latombe-Motwani-Raghavan/98,
AUTHOR = {Kavraki, Lydia E. and Latombe, Jean-Claude and Motwani, Rajeev and Raghavan, Prabhakar},
TITLE = {Randomized query processing in robot path planning},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {50-60},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kleinberg-Tardos/98,
AUTHOR = {Kleinberg, Jon and Tardos, {\'{E}}va},
TITLE = {Approximations for the disjoint paths problem in high-diameter planar networks},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {61-73},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Andersson-Hagerup-Nilsson-Raman/98,
AUTHOR = {Andersson, Arne and Hagerup, Torben and Nilsson, Stefan and Raman, Rajeev},
TITLE = {Sorting in linear time?},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {74-93},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Henzinger-Kopke-Puri-Varaiya/98,
AUTHOR = {Henzinger, Thomas A. and Kopke, Peter W. and Puri, Anuj and Varaiya, Pravin},
TITLE = {What's decidable about hybrid automata?},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {1},
PAGES = {94-124},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Agrawal-Allender-Rudich/98,
AUTHOR = {Agrawal, Manindra and Allender, Eric and Rudich, Steven},
TITLE = {Reductions in circuit complexity: An isomorphism theorem and a gap theorem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {127-143},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Barland-Kolaitis-Thakur/98,
AUTHOR = {Barland, Ian and Kolaitis, Phokion G. and Thakur, Madhukar N.},
TITLE = {Integer programming as a framework for optimization and approximability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {144-161},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Buss-Pitassi/98,
AUTHOR = {Buss, Samuel R. and Pitassi, Toniann},
TITLE = {Good degree bounds on Nullstellensatz refutations of the induction principle},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {162-171},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bach-Condon-Glaser-Tanguay/98,
AUTHOR = {Bach, Eric and Condon, Anne and Glaser, Elton and Tanguay, Celena},
TITLE = {DNA models and algorithms for $NP$-complete problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {172-186},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Feige-Kilian/98a,
AUTHOR = {Feige, Uriel and Kilian, Joe},
TITLE = {Zero knowledge and the chromatic number},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {187-199},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Caussinus-McKenzie-Therien-Vollmer/98,
AUTHOR = {Caussinus, Herv{\'{e}} and McKenzie, Pierre and Th{\'{e}}rien, Denis and Vollmer, Heribert},
TITLE = {Nondeterministic $NC^1$ computation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {200-212},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{van_Melkebeek/98,
AUTHOR = {van Melkebeek, Dieter},
TITLE = {Deterministic and randomized bounded truth-table reductions of $P$, $NL$, and $L$ to sparse sets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {2},
PAGES = {213-232},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bonner-Mecca/98,
AUTHOR = {Bonner, Anthony and Mecca, Giansalvatore},
TITLE = {Sequences, Datalog, and transducers},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {234-259},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Chaudhri-Hadzilacos/98,
AUTHOR = {Chaudhri, Vinay K. and Hadzilacos, Vassos},
TITLE = {Safe locking policies for dynamic databases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {260-271},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Consens-Milo/98,
AUTHOR = {Consens, Mariano P. and Milo, Tova},
TITLE = {Algebras for querying text regions: Expressive power and optimization},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {272-288},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Dong-Su/98,
AUTHOR = {Dong, Guozhu and Su, Jianwen},
TITLE = {Arity bounds in first-order incremental evaluation and definition of polynomial time database queries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {289-308},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Keidar-Dolev/98,
AUTHOR = {Keidar, Idit and Dolev, Danny},
TITLE = {Increasing the resilience of distributed and replicated database systems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {309-324},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Picouet-Vianu/98,
AUTHOR = {Picouet, Philippe and Vianu, Victor},
TITLE = {Semantics and expressiveness issues in active databases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {325-355},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Jain/98a,
AUTHOR = {Jain, Sanjay},
TITLE = {Learning with refutation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {356-365},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Hagerup-Katajainen-Nishimura-Ragde/98,
AUTHOR = {Hagerup, Torben and Katajainen, Jyrki and Nishimura, Naomi and Ragde, Prabhakar},
TITLE = {Characterizing multiterminal flow networks and computing flows in networks of small treewidth},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {366-375},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Auer-Long-Srinivasan/98,
AUTHOR = {Auer, Peter and Long, Philip M. and Srinivasan, Aravind},
TITLE = {Approximating hyper-rectangles: Learning and pseudorandom sets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {376-388},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Asarin-Maler/98,
AUTHOR = {Asarin, Eugene and Maler, Oded},
TITLE = {Achilles and the tortoise climbing up the arithmetical hierarachy},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {389-398},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Schulman/98,
AUTHOR = {Schulman, Leonard J.},
TITLE = {A three-party communication problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {57},
NUMBER = {3},
PAGES = {399-401},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Ginsburg-Wang/98,
AUTHOR = {Ginsburg, Seymour and Wang, X. Sean},
TITLE = {Regular sequence operations and their use in database queries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {1-26},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Satta/98,
AUTHOR = {Satta, Giorgio},
TITLE = {Trading independent for synchronized parallelism in finite copying parallel rewriting systems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {27-45},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Weber/98,
AUTHOR = {Weber, Andreas},
TITLE = {Transforming a single-valued transducer into a Mealey machine},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {46-59},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Manzini-Margara/98,
AUTHOR = {Manzini, Giovanni and Margara, Luciano},
TITLE = {Invertible linear cellular automata over $Z_m$: Algorithmic and dynamical aspects},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {60-67},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Rastogi-Mehrotra-Breitbart-Korth-Silberschatz/98,
AUTHOR = {Rastogi, Rajeev and Mehrotra, Sharad and Breitbart, Yuri and Korth, Henry F. and Silberschatz, Avi},
TITLE = {On correctness of nonserializable executions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {68-82},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Rajasekaran-Yooseph/98,
AUTHOR = {Rajasekaran, Sanguthevar and Yooseph, Shibu},
TITLE = {TAL recognition in $O(M(n^2))$ time},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {83-89},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Duris-Rolim/98,
AUTHOR = {{\v{D}}uri{\v{s}}, Pavol and Rolim, Jos{\'{e}} D.P.},
TITLE = {Lower bounds on the multiparty communication complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {90-95},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Ladner-LaMarca-Tempero/98,
AUTHOR = {Ladner, Richard E. and LaMarca, Anthony and Tempero, Ewan},
TITLE = {Counting protocols for reliable end-to-end transmission},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {96-111},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Bshouty-Bshouty/98,
AUTHOR = {Bshouty, Daoud and Bshouty, Nader H.},
TITLE = {On interpolating arithmetic read-once formulas with exponentiation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {112-124},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Kortelainen/98,
AUTHOR = {Kortelainen, Juha},
TITLE = {Remarks about commutative context-free languages},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {1},
PAGES = {125-129},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Ron-Singer-Tishby/98,
AUTHOR = {Ron, Dana and Singer, Yoram and Tishby, Naftali},
TITLE = {On the learnability and usage of acyclic probabilistic finite automata},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {2},
PAGES = {133-152},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Vovk/98,
AUTHOR = {Vovk, V.},
TITLE = {A game of prediction with expert advice},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {2},
PAGES = {153-173},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Bartlett-Long/98,
AUTHOR = {Bartlett, Peter L. and Long, Philip M.},
TITLE = {Prediction, learning, uniform convergence, and scale-sensitive dimensions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {2},
PAGES = {174-190},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Aslam-Decatur/98,
AUTHOR = {Aslam, Javed A. and Decatur, Scott E.},
TITLE = {Specification and simulation of statistical query algorithms for efficiency and noise tolerance},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {2},
PAGES = {191-208},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Blum-Chalasani-Goldman-Slonim/98,
AUTHOR = {Blum, Avrim and Chalasani, Prasad and Goldman, Sally A. and Slonim, Donna K.},
TITLE = {Learning with unreliable boundary queries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {2},
PAGES = {209-222},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Kim-Roche/98,
AUTHOR = {Kim, Jeong Han and Roche, James R.},
TITLE = {Covering cubes by random half cubes, with applications to binary neural networks},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {2},
PAGES = {223-252},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Ilie-Salomaa/98,
AUTHOR = {Ilie, Lucian and Salomaa, Arto},
TITLE = {2-testability and relabelings produce everything},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {253-262},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Berg-Ulfberg/98,
AUTHOR = {Berg, Christer and Ulfberg, Staffan},
TITLE = {A lower bound for perceptrons and an oracle separation of the $PP^{PH}$ hierarchy},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {263-271},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Sharma/98,
AUTHOR = {Sharma, Arun},
TITLE = {A note on batch and incremental learnability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {272-276},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Ben-David-Dichterman/98,
AUTHOR = {Ben-David, Shai and Dichterman, Eli},
TITLE = {Learning with restricted focus of attention},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {277-298},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Malvestuto-Moscarini/98,
AUTHOR = {Malvestuto, Francesco Mario and Moscarini, Marina},
TITLE = {A fast algorithm for query optimization in universal-relation databases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {299-309},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Bshouty-Hellerstein/98,
AUTHOR = {Bshouty, Nader and Hellerstein, Lisa},
TITLE = {Attribute-efficient learning in query and mistake-bound models},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {310-319},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Chen/98d,
AUTHOR = {Chen, Lin},
TITLE = {Optimal circular arc representations: Properties, recognition, and construction},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {320-331},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}
@article{Engelfriet-Vogler/98,
AUTHOR = {Engelfriet, Joost and Vogler, Heiko},
TITLE = {The equivalence of bottom-up and top-down tree-to-graph transducers},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {56},
NUMBER = {3},
PAGES = {332-356},
YEAR = {1998},
PUBLISHER = {Academic Press},
ADDRESS = {London-San Diego},
}