@article{Bloem-Engelfriet/00,
AUTHOR = {Bloem, Roderick and Engelfriet, Joost},
TITLE = {A comparison of tree transductions defined by monadic second order logic and by attribute grammars},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {1},
PAGES = {1-50},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Catalano-Gennaro/00,
AUTHOR = {Catalano, Dario and Gennaro, Rosario},
TITLE = {New efficient and secure protocols for verifiable signature sharing and other applications},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {1},
PAGES = {51-80},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Chari-Rohatgi-Srinivasan/00,
AUTHOR = {Chari, Suresh and Rohatgi, Pankaj and Srinivasan, Aravind},
TITLE = {Improved algorithms via approximations of probability distributions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {1},
PAGES = {81-107},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Paun/00,
AUTHOR = {P{\u{a}}un, Gheorghe},
TITLE = {Computing with membranes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {1},
PAGES = {108-143},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Bunemann-Fan-Weinstein/00,
AUTHOR = {Bunemann, Peter and Fan, Wenfei and Weinstein, Scott},
TITLE = {Path constraints in semistructured databases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {2},
PAGES = {146-193},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Agarwal-Arge-Erickson-Franciosa-Vitter/00,
AUTHOR = {Agarwal, Pankaj K. and Arge, Lars and Erickson, Jeff and Franciosa, Paulo G. and Vitter, Jeffrey Scott},
TITLE = {Efficient searching with linear constraints},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {2},
PAGES = {194-216},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Papadimitriou-Raghavan-Tamaki-Vempala/00,
AUTHOR = {Papadimitriou, Christos H. and Raghavan, Prabhakar and Tamaki, Hisao and Vempala, Santosh},
TITLE = {Latent semantic indexing: A probabilistic analysis},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {2},
PAGES = {217-235},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Abiteboul-Vianu-Fordham-Yesha/00,
AUTHOR = {Abiteboul, Serge and Vianu, Victor and Fordham, Brad and Yesha, Yelena},
TITLE = {Relational transducers for electronic commerce},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {2},
PAGES = {236-269},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Segoufin-Vianu/00,
AUTHOR = {Segoufin, Luc and Vianu, Victor},
TITLE = {Querying spatial databases via topological invariants},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {2},
PAGES = {270-301},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Kolaitis-Vardi/00,
AUTHOR = {Kolaitis, Phokion G. and Vardi, Moshe Y.},
TITLE = {Conjunctive-query containment and constraint satisfaction},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {2},
PAGES = {302-332},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Ambos-Spies-Bentzien/00,
AUTHOR = {Ambos-Spies, Klaus and Bentzien, Levke},
TITLE = {Separating $NP$-completeness notions under strong hypotheses},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {335-361},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Bellare-Kilian-Rogaway/00,
AUTHOR = {Bellare, Mihir and Kilian, Joe and Rogaway, Phillip},
TITLE = {The security of the cipher block chaining message authentication code},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {362-399},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Quaglia-Baldoni-Ciciani/00,
AUTHOR = {Quaglia, Francesco and Baldoni, Roberto and Ciciani, Bruno},
TITLE = {On the No-$Z$-Cycle property in distributed executions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {400-427},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Kearns-Ron/00,
AUTHOR = {Kearns, Michael and Ron, Dana},
TITLE = {Testing problems with sublearning sample complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {428-456},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Cheng-Chen-Tripathi/00,
AUTHOR = {Cheng, Sheng-Tzong and Chen, Chia-Mei and Tripathi, Satish K.},
TITLE = {A fault-tolerance model for multiprocessor real-time systems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {457-477},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Eiter-Ibaraki-Makino/00,
AUTHOR = {Eiter, Thomas and Ibaraki, Toshihide and Makino, Kazuhisa},
TITLE = {On the difference of Horn theories},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {478-507},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Larsen/00,
AUTHOR = {Larsen, Kim S.},
TITLE = {AVL trees with relaxed balance},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {508-522},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Takeuchi-Abe-Amari/00,
AUTHOR = {Takeuchi, Jun-ichi and Abe, Naoki and Amari, Shun-ichi},
TITLE = {The Lob-Pass problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {523-557},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Bollig-Wegener/00,
AUTHOR = {Bollig, Beate and Wegener, Ingo},
TITLE = {Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {61},
NUMBER = {3},
PAGES = {558-579},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Ma-Wang/00,
AUTHOR = {Ma, Bin and Wang, Lusheng},
TITLE = {On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {1-12},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Fokkink/00,
AUTHOR = {Fokkink, Wan},
TITLE = {Rooted branching bisimulation as a congruence},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {13-37},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Cao/00,
AUTHOR = {Cao, Jinde},
TITLE = {Global exponential stability and periodic solutions of delayed cellular neural networks},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {38-46},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Okamoto/00,
AUTHOR = {Okamoto, Tatsuaki},
TITLE = {On relationships between statistical zero-knowledge proofs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {47-108},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Lange-Niedermeier/00,
AUTHOR = {Lange, Klaus-J{\"o}rn and Niedermeier, Rolf},
TITLE = {Data independence of read, write, and control structures in PRAM computations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {109-144},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Bekesi-Galambos-Kellerer/00,
AUTHOR = {B{\'{e}}k{\'{e}}si, J{\'{o}}zsef and Galambos, G{\'{a}}bor and Kellerer, Hans},
TITLE = {A 5/4 linear time bin packing algorithm},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {145-160},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Servedio/00,
AUTHOR = {Servedio, Rocco A.},
TITLE = {Computational sample complexity and attribute-efficient learning},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {161-178},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Cao-Tao/00,
AUTHOR = {Cao, Jinde and Tao, Qing},
TITLE = {Estimation of the domain of attraction and the convergence rate of a Hopfield associative memory and an application},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {179-186},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Baier-Engelen-Majster-Cederbaum/00,
AUTHOR = {Baier, Christel and Engelen, Bettina and Majster-Cederbaum, Mila},
TITLE = {Deciding bisimilarity and similarity for probabilistic processes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {1},
PAGES = {187-231},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Case-Jain-Ott-Sharma-Stephan/00,
AUTHOR = {Case, John and Jain, Sanjay and Ott, Matthias and Sharma, Arun and Stephan, Frank},
TITLE = {Robust learning aided by context},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {234-257},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Birkendorf-Klasner-Kuhlmann-Simon/00,
AUTHOR = {Birkendorf, Andreas and Klasner, Norbert and Kuhlmann, Christian and Simon, Hans U.},
TITLE = {Structural results about exact learning with unspecified attribute values},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {258-277},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Rosin/00,
AUTHOR = {Rosin, Christopher D.},
TITLE = {Sample complexity of model-based search},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {278-301},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Reischuk-Zeugmann/00,
AUTHOR = {Reischuk, R{\"u}diger and Zeugmann, Thomas},
TITLE = {An average-case optimal one-variable pattern language learner},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {302-335},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Fortnow/00a,
AUTHOR = {Fortnow, Lance},
TITLE = {Time-space tradeoffs for satisfiability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {337-353},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Lange-McKenzie-Tapp/00,
AUTHOR = {Lange, Klaus-J{\"o}rn and McKenzie, Pierre and Tapp, Alain},
TITLE = {Reversible space equals deterministic space},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {354-367},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Moore-Therien-Lemieux-Berman-Drisko/00,
AUTHOR = {Moore, Cristopher and Th{\'{e}}rien, Denis and Lemieux, Fran{\c{c}}ois and Berman, Joshua and Drisko, Arthur},
TITLE = {Circuits and expressions with nonassociative gates},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {368-394},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Agrawal-Allender-Datta/00,
AUTHOR = {Agrawal, Manindra and Allender, Eric and Datta, Samir},
TITLE = {On $TC^0, AC^0$, and arithmetic circuits},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {395-421},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Beigel-Fu/00,
AUTHOR = {Beigel, Richard and Fu, Bin},
TITLE = {Circuits over $PP$ and $PL$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {422-441},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Hammer-Romashchenko-Shen-Vereshchagin/00,
AUTHOR = {Hammer, Daniel and Romashchenko, Andrei and Shen, Alexander and Vereshchagin, Nikolai},
TITLE = {Inequalities for Shannon entropy and Kolmogorov complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {442-464},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Downey-Nies/00,
AUTHOR = {Downey, Rod and Nies, Andr{\'{e}}},
TITLE = {Undecidability results for low complexity time classes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {2},
PAGES = {465-479},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Aiello-Kushilevitz-Ostrovsky-Rosen/00,
AUTHOR = {Aiello, William and Kushilevitz, Eyal and Ostrovsky, Rafail and Ros{\'{e}}n, Adi},
TITLE = {Adaptive packet routing for bursty adversarial traffic},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {482-509},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Feige/00,
AUTHOR = {Feige, Uriel},
TITLE = {Approximating the bandwidth via volume respecting embeddings},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {510-539},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Goldreich-Goldwasser/00,
AUTHOR = {Goldreich, Oded and Goldwasser, Shafi},
TITLE = {On the limits of nonapproximability of lattice problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {540-563},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Galinescu-Karloff-Rabani/00,
AUTHOR = {G{\u{a}}linescu, Gruia and Karloff, Howard and Rabani, Yuval},
TITLE = {An improved approximation algorithm for $\sc Multiway$ $\sc Cut$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {564-574},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Khanna-Zhou/00,
AUTHOR = {Khanna, Sanjeev and Zhou, Shiyu},
TITLE = {On indexed data broadcast},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {575-591},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Gertner-Ishai-Kushilevitz-Malkin/00,
AUTHOR = {Gertner, Yael and Ishai, Yuval and Kushilevitz, Eyal and Malkin, Tal},
TITLE = {Protecting data privacy in privat information retrieval schemes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {592-629},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Broder-Charikar-Frieze-Mitzenmacher/00,
AUTHOR = {Broder, Andrei Z. and Charikar, Moses and Frieze, Alan M. and Mitzenmacher, Michael},
TITLE = {Min-wise independent permutations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {630-659},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Ajtai-Fagin-Stockmeyer/00,
AUTHOR = {Ajtai, Miklos and Fagin, Ronald and Stockmeyer, Larry},
TITLE = {The closure of monadic $NP$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {660-716},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Ergun-Kannan-Kumar-Rubinfeld-Viswanathan/00,
AUTHOR = {Erg{\"u}n, Funda and Kannan, Sampath and Kumar, S. Ravi and Rubinfeld, Ronitt and Viswanathan, Mahesh},
TITLE = {Spot-checkers},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {60},
NUMBER = {3},
PAGES = {717-751},
YEAR = {2000},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}