@article{Vikas/96,
AUTHOR = {Vikas, Narayan},
TITLE = {An $O(n)$ algorithm for Abelian $p$-group isomorphism and an $O(n\log n)$ algorithm for Abelian group isomorphism},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {1-9},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Shallit-Breitbart/96,
AUTHOR = {Shallit, Jeffrey and Breitbart, Yuri},
TITLE = {Automaticity I: Properties of a measure of descriptional complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {10-25},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Baliga-Case/96,
AUTHOR = {Baliga, Ganesh and Case, John},
TITLE = {Learnability: Admissible, co-finite, and hypersimple languages},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {26-32},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Drewes/96,
AUTHOR = {Drewes, Frank},
TITLE = {Language theoretic and algorithmic properties of $d$-dimensional collages and patterns in a grid},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {33-60},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Moran-Taubenfeld-Yadin/96,
AUTHOR = {Moran, Shlomo and Taubenfeld, Gadi and Yadin, Irit},
TITLE = {Concurrent counting},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {61-78},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Sieling/96,
AUTHOR = {Sieling, Detlef},
TITLE = {New lower bounds and hierarchy results for restricted branching programs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {79-87},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Lange-Zeugmann/96,
AUTHOR = {Lange, Steffen and Zeugmann, Thomas},
TITLE = {Incremental learning from positive data},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {88-103},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Fich-Impagliazzo-Kapron-King-Kutylowski/96,
AUTHOR = {Fich, Faith E. and Impagliazzo, Russell and Kapron, Bruce and King, Valerie and Kuty{\l}owski, Miros{\l}aw},
TITLE = {Limits on the power of parallel random access machines with weak forms of write conflict resolution},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {104-111},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Gao/96,
AUTHOR = {Gao, Feng},
TITLE = {Towards structured parallel computing on architecture-independent parallel algorithm design for distributed-memory architectures},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {112-128},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Gabow-Xu/96,
AUTHOR = {Gabow, Harold N. and Xu, Ying},
TITLE = {Efficient theoretic and practical algorithms for linear matroid intersection problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {129-147},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Dietz/96,
AUTHOR = {Dietz, Paul F.},
TITLE = {A space efficient variant of path copying for partially persistent sorted sets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {1},
PAGES = {148-152},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Agrawal-Biswas/96,
AUTHOR = {Agrawal, Manindra and Biswas, Somenath},
TITLE = {Polynomial-time isomorphism of 1-L-complete sets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {155-160},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Papadimitriou-Yannakakis/96,
AUTHOR = {Papadimitriou, Christos H. and Yannakakis, Mihalis},
TITLE = {On limited nondeterminism and the complexity of the V-C dimension},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {161-170},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Ogihara-Thierauf-Toda-Watanabe/96,
AUTHOR = {Ogihara, Mitsunori and Thierauf, Thomas and Toda, Seinosuke and Watanabe, Osamu},
TITLE = {On clusure properties of $\#\P$ in the context of $PF\circ\#\P$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {171-179},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Hirst-Harel/96a,
AUTHOR = {Hirst, Tirza and Harel, David},
TITLE = {Taking it to the limit: On infinite variants of $NP$-complete problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {180-193},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Hemaspaandra-Naik-Ogihara-Selman/96,
AUTHOR = {Hemaspaandra, Edith and Naik, Ashish V. and Ogihara, Mitsunori and Selman, Alan L.},
TITLE = {$\P$-selective sets and reducing search to decision vs self-reducibility},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {194-209},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Buhrman-Torenvliet/96,
AUTHOR = {Buhrman, Harry and Torenvliet, Leen},
TITLE = {$\P$-selective self-reducible sets: A new characterization of $\P$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {210-217},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Dymond-Fich-Nishimura-Ragde-Ruzzo/96,
AUTHOR = {Dymond, Patrick W. and Fich, Faith E. and Nishimura, Naomi and Ragde, Prabhakar and Ruzzo, Walter L.},
TITLE = {Pointers versus arithmetic in PRAMs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {218-232},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Eighth Annual Conference on Structure in Complexity Theory 1993},
}
@article{Kautz-Miltersen/96,
AUTHOR = {Kautz, Steven M. and Miltersen, Peter Bro},
TITLE = {Relative to a random oracle, $NP$ is not small},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {235-250},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Ninth Annual Conference on Structure in Complexity Theory 1994},
}
@article{Tardos/96,
AUTHOR = {Tardos, G{\'{a}}bor},
TITLE = {Multi-prover encoding schemes and three-prover proof systems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {251-260},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Ninth Annual Conference on Structure in Complexity Theory 1994},
}
@article{Buhrman-Orponen/96,
AUTHOR = {Buhrman, Harry and Orponen, Pekka},
TITLE = {Random strings make hard instances},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {261-266},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Ninth Annual Conference on Structure in Complexity Theory 1994},
}
@article{Agrawal/96,
AUTHOR = {Agrawal, Manindra},
TITLE = {On the isomorphism conjecture for weak reducibilities},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {267-282},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Ninth Annual Conference on Structure in Complexity Theory 1994},
}
@article{Compton-Gradel/96,
AUTHOR = {Compton, Kevin J. and Gr{\"a}del, Erich},
TITLE = {Logical definability of counting functions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {283-297},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Ninth Annual Conference on Structure in Complexity Theory 1994},
}
@article{Chang/96,
AUTHOR = {Chang, Richard},
TITLE = {On the query complexity of clique size and maximum satisfiability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {2},
PAGES = {298-313},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also Ninth Annual Conference on Structure in Complexity Theory 1994},
}
@article{Mitzenmacher/96a,
AUTHOR = {Mitzenmacher, Michael},
TITLE = {Bounds on the greedy routing algorithm for array networks},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {317-327},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Schwabe-Sutherland/96,
AUTHOR = {Schwabe, Eric J. and Sutherland, Ian M.},
TITLE = {Improved parity-declustered layouts for disk arrays},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {328-343},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Reid-Miller/96,
AUTHOR = {Reid-Miller, Margaret},
TITLE = {List ranking and list scan on the CRAY C90},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {344-356},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Ghosh-Muthukrishnan/96,
AUTHOR = {Ghosh, Bhaskar and Muthukrishnan, S.},
TITLE = {Dynamic load balancing by random matchings},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {357-370},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Tamaki/96,
AUTHOR = {Tamaki, Hisao},
TITLE = {Construction of the mesh and the torus tolerating a large number of faults},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {371-379},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Leoncini/96a,
AUTHOR = {Leoncini, M.},
TITLE = {On the parallel complexity of Gaussian elimination with pivoting},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {380-394},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Halperin-Zwick/96,
AUTHOR = {Halperin, Shay and Zwick, Uri},
TITLE = {An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {395-416},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Gibbons-Matias-Ramachandran/96,
AUTHOR = {Gibbons, Phillip B. and Matias, Yossi and Ramachandran, Vijaya},
TITLE = {Efficient low-contention parallel algorithms},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {417-442},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Meghini-Thanos/96,
AUTHOR = {Meghini, Carlo and Thanos, Costantino},
TITLE = {An optimal predicate locking scheduler},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {443-468},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Goerdt/96,
AUTHOR = {Goerdt, Andreas},
TITLE = {A threshold for unsatisfiability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {469-486},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Kari-Thierrin/96,
AUTHOR = {Kari, Lila and Thierrin, Gabriel},
TITLE = {Maximal and minimal solutions to language equations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {487-496},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Eiter-Gottlob/96,
AUTHOR = {Eiter, Thomas and Gottlob, Georg},
TITLE = {The complexity of nested counterfactuals and iterated knowledge base revisions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {497-512},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Jiang-Li/96,
AUTHOR = {Jiang, Tao and Li, Ming},
TITLE = {$k$ one-way heads cannot do string-matching},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {513-524},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Blair-Lloyd/96,
AUTHOR = {Blair, Jean R.S. and Lloyd, Errol L.},
TITLE = {River routing with a generalized model},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {525-544},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Chari-Rohatgi/96,
AUTHOR = {Chari, Suresh and Rohatgi, Pankaj},
TITLE = {On completeness under random reductions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {545-555},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Engelfriet-Oostrom/96,
AUTHOR = {Engelfriet, Joost and Oostrom, Vincent van},
TITLE = {Regular description of context-free graph languages},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {556-574},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Grzymala-Busse-Than/96,
AUTHOR = {Grzymala-Busse, Jerzy W. and Than, Soe},
TITLE = {Partition triples: A tool for reduction of data sets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {575-582},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Jain/96,
AUTHOR = {Jain, Sanjay},
TITLE = {Program synthesis in the presence of infinite number of inaccuracies},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {53},
NUMBER = {3},
PAGES = {583-591},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see also 1994 ACM Symposium on Parallel Algorithms and Architectures},
}
@article{Eppstein-Galil-Italiano-Spencer/96,
AUTHOR = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Spencer, Thomas H.},
TITLE = {Separator based sparsification --- I. Planarity testing and minimum spanning trees},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {3-27},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Baker/96,
AUTHOR = {Baker, Brenda S.},
TITLE = {Parameterized pattern matching: Algorithms and applications},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {28-42},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Nisan-Zuckerman/96,
AUTHOR = {Nisan, Noam and Zuckerman, David},
TITLE = {Randomness is linear in space},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {43-52},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Pippenger/96,
AUTHOR = {Pippenger, Nicholas},
TITLE = {Self-routing superconcentrators},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {53-60},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Cherubini-San_Pietro/96,
AUTHOR = {Cherubini, Alessandra and San Pietro, Pierluigi},
TITLE = {A polynomial-time parsing algorithm for $K$-depth languages},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {61-79},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Chen/96d,
AUTHOR = {Chen, Tsong Yueh},
TITLE = {On the structural properties of the set of fixpoints for nondeterministic recursive definitions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {80-86},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{La_Poutre/96,
AUTHOR = {La Poutr{\'e}, Han},
TITLE = {Lower bounds for the union-find and the split-find problem on pointer machines},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {87-99},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Krishnamurthy-Ramakrishnan-Shmueli/96,
AUTHOR = {Krishnamurthy, Ravi and Ramakrishnan, Raghu and Shmueli, Oded},
TITLE = {A framework for testing safety and effective computability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {100-124},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Libkin-Wong/96,
AUTHOR = {Libkin, Leonid and Wong, Limsoon},
TITLE = {Semantic representations and query languages for or-sets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {125-142},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Astesiano-Zucca/96,
AUTHOR = {Astesiano, Egidio and Zucca, Elena},
TITLE = {A free construction of dynamic terms},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {143-156},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Willard/96,
AUTHOR = {Willard, Dan E.},
TITLE = {Applications of range query theory to relational data base join and selection operations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {157-169},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Ehrenfeucht-Engelfriet-Rozenberg/96,
AUTHOR = {Ehrenfeucht, Andrzej and Engelfriet, Joost and Rozenberg, Grzegorz},
TITLE = {Finite languages for the representation of finite graphs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {170-184},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Honkala/96,
AUTHOR = {Honkala, Juha},
TITLE = {On Parik slender languages and power series},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {185-190},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Fortnow-Yamakami/96,
AUTHOR = {Fortnow, Lance and Yamakami, Tomoyuki},
TITLE = {Generic separations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {1},
PAGES = {191-197},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Schapire-Sellie/96,
AUTHOR = {Schapire, Robert E. and Sellie, Linda M.},
TITLE = {Learning sparse multivariate polynomials over a field with queries and counterexamples},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {201-213},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kummer-Stephan/96,
AUTHOR = {Kummer, Martin and Stephan, Frank},
TITLE = {On the structure of degrees of inferability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {214-238},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Simon/96,
AUTHOR = {Simon, Hans Ulrich},
TITLE = {General bounds on the number of examples needed for learning probabilistic concepts},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {239-254},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Goldman-Mathias/96,
AUTHOR = {Goldman, Sally A. and Mathias, H. David},
TITLE = {Teaching a smarter learner},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {255-267},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bshouty-Goldman-Hancock-Matar/96,
AUTHOR = {Bshouty, Nader H. and Goldman, Sally A. and Hancock, Thomas R. and Matar, Sleiman},
TITLE = {Asking questions to minimize errors},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {268-286},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kshemkalyani/96,
AUTHOR = {Kshemkalyani, Ajay D.},
TITLE = {Temporal interactions of intervals in distributed systems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {287-298},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Amir-Benson-Farach/96,
AUTHOR = {Amir, Amihood and Benson, Gary and Farach, Martin},
TITLE = {Let sleeping files lie: Pattern matching in Z-compressed files},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {299-307},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Schuler-Yamakami/96,
AUTHOR = {Schuler, Rainer and Yamakami, Tomoyuki},
TITLE = {Structural average case complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {308-327},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Vaishnavi/96,
AUTHOR = {Vaishnavi, Vijay K.},
TITLE = {On $k$-dimensional balanced binary trees},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {328-348},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Gibson/96,
AUTHOR = {Gibson, Gavin J.},
TITLE = {Exact classification with two-layer neural nets},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {349-356},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Andries-Paredaens/96,
AUTHOR = {Andries, Marc and Paredaens, Jan},
TITLE = {On instance-completeness for database query languages involving object creation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {357-373},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Fang-Venkatesh/96,
AUTHOR = {Fang, Shao C. and Venkatesh, Santosh S.},
TITLE = {Learning binary perceptrons perfectly efficiently},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {2},
PAGES = {374-389},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Jain-Sharma/96,
AUTHOR = {Jain, Sanjay and Sharma, Arun},
TITLE = {The intrinsic complexity of language identification},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {393-402},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kummer-Stephan/96a,
AUTHOR = {Kummer, Martin and Stephan, Frank},
TITLE = {Inclusion problems in parallel learning and games},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {403-420},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bshouty-Cleve-Gavalda-Kannan-Tamon/96,
AUTHOR = {Bshouty, Nader H. and Cleve, Richard and Gavald{\`{a}}, Ricard and Kannan, Sampath and Tamon, Christino},
TITLE = {Oracles and queries that are sufficient for exact learning},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {421-433},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bartlett-Long-Williamson/96,
AUTHOR = {Bartlett, Peter L. and Long, Philip M. and Williamson, Robert C.},
TITLE = {Fat-shattering and the learnability of real-valued functions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {434-452},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Dobkin-Gunopulos-Maass/96,
AUTHOR = {Dobkin, David P. and Gunopulos, Dimitrios and Maass, Wolfgang},
TITLE = {Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {453-470},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Frazier-Goldman-Mishra-Pitt/96,
AUTHOR = {Frazier, Michael and Goldman, Sally and Mishra, Nina and Pitt, Leonard},
TITLE = {Learning from a consistently ignorant teacher},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {471-492},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Wong/96,
AUTHOR = {Wong, Limsoon},
TITLE = {Normal forms and conservative extension properties for query languages over collection types},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {495-505},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Morishita/96,
AUTHOR = {Morishita, Shinichi},
TITLE = {An extension of Van Gelder's alternating fixpoint to magic programs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {506-521},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Hirst-Harel/96,
AUTHOR = {Hirst, Tirza and Harel, David},
TITLE = {Completeness results for recursive data bases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {522-536},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Van_den_Bussche-Gucht-Vossen/96,
AUTHOR = {Van den Bussche, Jan and Gucht, Dirk van and Vossen, Gottfried},
TITLE = {Reflective programming in the relational algebra},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {537-549},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Haas-Naughton-Seshadri-Swami/96,
AUTHOR = {Haas, Peter J. and Naughton, Jeffrey F. and Seshadri, S. and Swami, Arun N.},
TITLE = {Selectivity and cost estimation for joins based on random sampling},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {550-569},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Grumbach-Milo/96,
AUTHOR = {Grumbach, St{\'{e}}phane and Milo, Tova},
TITLE = {Towards tractable algebras for bags},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {570-588},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kanellakis-Ramaswamy-Vengroff-Vitter/96,
AUTHOR = {Kanellakis, Paris and Ramaswamy, Sridhar and Vengroff, Darren E. and Vitter, Jeffrey Scott},
TITLE = {Indexing for data models with constraints and classes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {52},
NUMBER = {3},
PAGES = {589-612},
YEAR = {1996},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}