@article{Ajtai/02a,
AUTHOR = {Ajtai, Mikl{\'{o}}s},
TITLE = {Determinism verus nondeterminism for linear time RAMs with memory restrictions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {1},
PAGES = {2-37},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Beame-Fich/02,
AUTHOR = {Beame, Paul and Fich, Faith E.},
TITLE = {Optimal bounds for the predecessor problem and related problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {1},
PAGES = {38-72},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Li-Ma-Wang/02a,
AUTHOR = {Li, Ming and Ma, Bin and Wang, Lusheng},
TITLE = {Finding similar regions in many sequences},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {1},
PAGES = {73-96},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Raz-Reingold-Vadhan/02,
AUTHOR = {Raz, Ran and Reingold, Omer and Vadhan, Salil},
TITLE = {Extracting all the randomness and reducing the error in Trevisan's extractors},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {1},
PAGES = {97-128},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Charikar-Guha-Tardos-Shmoys/02,
AUTHOR = {Charikar, Moses and Guha, Sudipto and Tardos, {\'{E}}va and Shmoys, David B.},
TITLE = {A constant-factor approximation algorithm for the $k$-median problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {1},
PAGES = {129-149},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{King-Sagert/02,
AUTHOR = {King, Valerie and Sagert, Garry},
TITLE = {A fully dynamic algorithm for maintaining the transitive closure},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {1},
PAGES = {150-167},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Stewart/02,
AUTHOR = {Stewart, Charles},
TITLE = {Reducibility between classes of port graph grammar},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {169-223},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Nakamura-Abe/02,
AUTHOR = {Nakamura, Atsuyoshi and Abe, Naoki},
TITLE = {Online learning of binary and $n$-ary relations over clustered domains},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {224-256},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Arvind-Kobler/02,
AUTHOR = {Arvind, V. and K{\"o}bler, Johannes},
TITLE = {New lowness results for $ZPP^{NP}$ and other complexity classes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {257-277},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Harju-Ibarra-Karhumaki-Salomaa/02,
AUTHOR = {Harju, Tero and Ibarra, Oscar and Karhum{\"a}ki, Juhani and Salomaa, Arto},
TITLE = {Some decision problems concerning semilinearity and commutation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {278-294},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Willard/02,
AUTHOR = {Willard, Dan E.},
TITLE = {An algorithm for handling many relational calculus queries efficiently},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {295-331},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Berman-Karpinski-Larmore-Plandowski-Rytter/02,
AUTHOR = {Berman, Piotr and Karpinski, Marek and Larmore, Lawrence L. and Plandowski, Wojciech and Rytter, Wojciech},
TITLE = {On the complexity of pattern matching for highly compressed two-dimensional texts},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {332-350},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Skodinis-Wanke/02,
AUTHOR = {Skodinis, K. and Wanke, E.},
TITLE = {Node replacements in embedding normal form},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {351-376},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Honkala/02b,
AUTHOR = {Honkala, Juha},
TITLE = {The equivalence problem for DF0L languages and power series},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {377-392},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Pighizzini-Shallit-Wang/02,
AUTHOR = {Pighizzini, Giovanni and Shallit, Jeffrey and Wang, Ming-wei},
TITLE = {Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {393-414},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Mason-Bartlett-Golea/02,
AUTHOR = {Mason, Llew and Bartlett, Peter L. and Golea, Mostefa},
TITLE = {Generalization error of combined classifiers},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {2},
PAGES = {415-438},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{El-Mabrouk/02,
AUTHOR = {El-Mabrouk, Nadia},
TITLE = {Reconstructing an ancestral genome using minimum segments duplications and reversals},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {442-464},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Lin-Chen-Jiang-Wen/02,
AUTHOR = {Lin, Guohui and Chen, Zhi-Zhong and Jiang, Tao and Wen, Jianjun},
TITLE = {The longest common subsequence problem for sequences with nested arc annotations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {465-480},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Lagergren/02,
AUTHOR = {Lagergren, J.},
TITLE = {Combining polynomial running time and fast convergence for the disk-covering method},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {481-493},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Jaitly-Kearney-Lin-Ma/02,
AUTHOR = {Jaitly, Deep and Kearney, Paul and Lin, Guohui and Ma, Bin},
TITLE = {Methods for reconstructing the history of tandem repeats and their application to the human genome},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {494-507},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Moret-Tang-Wang-Warnow/02,
AUTHOR = {Moret, Bernard M.E. and Tang, Jijun and Wang, Li-San and Warnow, Tandy},
TITLE = {Steps toward accurate reconstructions of phylogenies from gene-order data},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {508-525},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Pandurangan-Ramesh/02,
AUTHOR = {Pandurangan, Gopal and Ramesh, H.},
TITLE = {The restriction mapping problem revisited},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {526-544},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Lyngso-Pedersen/02,
AUTHOR = {Lyngs{\o}, Rune B. and Pedersen, Christian N.S.},
TITLE = {The consensus string problem and the complexity of comparing hidden Markov models},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {545-569},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Lin-Jiang-Chao/02,
AUTHOR = {Lin, Yaw-Ling and Jiang, Tao and Chao, Kun-Mao},
TITLE = {Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {570-586},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Tesler/02a,
AUTHOR = {Tesler, Glenn},
TITLE = {Efficient algorithms for multichromosomal genome rearrangements},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {3},
PAGES = {587-609},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Forster/02,
AUTHOR = {Forster, J{\"u}rgen},
TITLE = {A linear lower bound on the unbounded error probabilistic communication complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {612-625},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Atserias-Galesi-Pudlak/02,
AUTHOR = {Atserias, Albert and Galesi, Nicola and Pudl{\'{a}}k, Pavel},
TITLE = {Monotone simulations of non-monotone proofs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {626-638},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Shpilka/02,
AUTHOR = {Shpilka, Amir},
TITLE = {Affine projections of symmetric polynomials},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {639-659},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Mossel-Umans/02,
AUTHOR = {Mossel, Elchanan and Umans, Christopher},
TITLE = {On the complexity of approximating the VC dimension},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {660-671},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Impagliazzo-Kabanets-Wigderson/02,
AUTHOR = {Impagliazzo, Russell and Kabanets, Valentine and Wigderson, Avi},
TITLE = {In search of an easy witness: Exponential time vs. probabilistic polynomial time},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {672-694},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}
@article{Hesse-Allender-Barrington/02,
AUTHOR = {Hesse, William and Allender, Eric and Barrington, David A. Mix},
TITLE = {Uniform constant-depth threshold circuits for division and iterated multiplication},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {695-716},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
NOTE = {see Corrigendum in J. Comput.~Syst.~Sci., Vol. 80, 2014, No. 2, 496-497},
}
@article{Koucky/02,
AUTHOR = {Kouck{\'y}, Michal},
TITLE = {Universal traversal sequences with backtracking},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {65},
NUMBER = {4},
PAGES = {717-726},
YEAR = {2002},
PUBLISHER = {Academic Press},
ADDRESS = {San Diego-London},
}